[编程题]排序
Go 语言 - 归并排序
package main
import "fmt"
// 归并排序
func mergeSort(nums []int) []int {
numsLen := len(nums)
if numsLen < 2 {
return nums
}
middleIndex := numsLen / 2
left := nums[: middleIndex]
right := nums[middleIndex:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1: ]
} else {
result = append(result, right[0])
right = right[1: ]
}
}
if len(left) != 0 {
result = append(result, left...)
}
if len(right) != 0 {
result = append(result, right...)
}
return result
}
func main(){
var n int
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
var tmp int
fmt.Scan(&tmp)
nums[i] = tmp
}
res := mergeSort(nums)
for _, num := range res {
fmt.Print(num, " ")
}
} Go 语言 - 快速排序
package main
import "fmt"
// 快速排序
func quickSort(nums []int)[]int{
return _quickSort(nums, 0, len(nums) - 1)
}
func _quickSort(nums []int, left, right int) []int {
if left < right {
partitionIndex := partition(nums, left, right)
_quickSort(nums, left, partitionIndex-1)
_quickSort(nums, partitionIndex+1, right)
}
return nums
}
func partition(nums []int, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if nums[pivot] > nums[i] {
nums[i], nums[index] = nums[index], nums[i]
index++
}
}
nums[pivot], nums[index - 1] = nums[index - 1], nums[pivot]
return index - 1
}
func main(){
var n int
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
var tmp int
fmt.Scan(&tmp)
nums[i] = tmp
}
res := quickSort(nums)
for _, num := range res {
fmt.Print(num, " ")
}
}
发表于 2020-08-29 16:33:28
回复(0)
Java ，使用JavaAPI，冒泡排序，选择排序，插入排序，堆排序，归并排序，快速排序 七种解法
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int[] array;
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
array = new int[n];
for (int i = 0; i < n; i++) array[i] = scanner.nextInt();
// apiSort();
// bubbleSort();
// selectSort();
// insertSort();
// heapSort();
// mergeSort(0, n - 1);
quickSort(0, n - 1);
for (int i : array) System.out.print(i + " ");
}
// 使用Java APi
static void apiSort() {
Arrays.sort(array);
}
// 交换两个数
static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 冒泡排序
static void bubbleSort() {
// 每趟往前归位一个最小值
for (int i = 1; i < n; i++)
for (int j = n - 1; j >= i; j--)
if (array[j] < array[j - 1]) swap(j, j - 1);
}
// 选择排序
static void selectSort() {
for (int i = 0; i < n - 1; i++) {
int k = i;
for (int j = i; j <= n - 1; j++)
if (array[j] < array[k]) k = j;
swap(k, i);
}
}
// 插入排序
static void insertSort() {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) swap(j, j - 1);
else break;
}
}
}
// 堆排序
static void heapSort() {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i : array) minHeap.add(i);
for (int i = 0; i < n; i++) array[i] = minHeap.poll();
}
// 归并排序
static void mergeSort(int i, int j) {
if (i >= j) return;
int mid = (i + j) >> 1;
mergeSort(i, mid);
mergeSort(mid + 1, j);
merge(i, mid, j);
}
static void merge(int i, int mid, int j) {
int[] temp = new int[n];
int l = i;
int r = mid + 1;
int t = i;
while (l <= mid && r <= j) temp[t++] = array[l] <= array[r] ? array[l++] : array[r++];
while (l <= mid) temp[t++] = array[l++];
while (r <= j) temp[t++] = array[r++];
System.arraycopy(temp, i, array, i, j - i + 1);
}
// 快速排序
static void quickSort(int i, int j) {
if (i >= j) return;
int pivot = partition(i, j);
quickSort(i, pivot - 1);
quickSort(pivot + 1, j);
}
static int partition(int i, int j) {
int v = array[i];
int l = i + 1;
int r = j;
while (true) {
while (l <= j && array[l] <= v) l++;
while (r >= i + 1 && array[r] >= v) r--;
if (l > r) break;
swap(l++, r--);
}
swap(i, r);
return r;
}
}
发表于 2020-03-17 20:51:44
回复(0)
# include<stdio.h>
# include<algorithm>
using namespace std;
int main()
{
int n;
int buf[10000];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&buf[i]);
}
sort(buf,buf+n);
for(int i=0;i<n;i++)
{
printf("%d ",buf[i]);
}
printf("\n");
}
return 0;
}
# include<algorithm>
using namespace std;
int main()
{
int n;
int buf[10000];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&buf[i]);
}
sort(buf,buf+n);
for(int i=0;i<n;i++)
{
printf("%d ",buf[i]);
}
printf("\n");
}
return 0;
}
// 如果遇到N比较大的情况下，可以用sort函数
发表于 2018-02-15 12:31:02
回复(0)
注意一下每个数字后面都有空格（包括一行末尾的数字后面也有空格）即可
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int n, a[101];
while(scanf("%d", &n)!=EOF) {
for(int i=0; i<n; i++) scanf("%d", &a[i]);
sort(a, a+n);
for(int i=0; i<n; i++) printf("%d ", a[i]);
printf("\n");
}
return 0;
}
编辑于 2018-02-06 20:26:45
回复(0)
int main(){
int buf[100],n,i,j;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
scanf("%d",&buf[i]);
sort(buf,buf+n);
for(j=0;j<n;j++)
printf("%d ",buf[j]);
printf("\n");
}
return 0;
int buf[100],n,i,j;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
scanf("%d",&buf[i]);
sort(buf,buf+n);
for(j=0;j<n;j++)
printf("%d ",buf[j]);
printf("\n");
}
return 0;
}
1.使用c++库algorithm实现排序
2.while控制一轮输入 ，int n 和n 个数是一个整体 因此while 循环的花括号需要将控制一轮循环的代码括起来 输入n为EOF时whlie条件失效return 0；结束整个程序进程
发表于 2018-01-15 11:21:44
回复(0)
#include<stdio.h>
int main()
{
int a[100],n,i,j,t;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
int main()
{
int a[100],n,i,j,t;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
发表于 2017-12-30 21:16:29
回复(0)
import java.util.*;
public class Main{
public static void quickSort(int[] arr, int first, int last){
if(first >= last) return;
int pivot = arr[first], l = first, h = last;
while(l < h){
while(l < h && pivot <= arr[h]) h--;
arr[l] = arr[h];
while(l < h && pivot >= arr[l]) l++;
arr[h] = arr[l];
}
arr[l] = pivot;
quickSort(arr, first, l - 1);
quickSort(arr, l + 1, last);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int[] arr = new int[101];
while(in.hasNext()){
int n = in.nextInt();
for(int i = 0; i < n; i++){
arr[i] = in.nextInt();
}
quickSort(arr, 0, n-1);
for(int i = 0; i < n; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
}
编辑于 2017-05-20 16:58:29
回复(0)
#include <stdio.h>
#include <stdlib.h> //包含qsort的头文件
//比较函数
int Cmp(const void *pa, const void *pb)
{
return *(int*)pa > *(int*)pb;
}
int main(){
int n;
int arr[10000];
//输入数据
while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//使用qsort排序算法
qsort(arr, n, sizeof(int), Cmp);
//输出数据
for (i=0; i<n; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
return 0;
}
#include <stdlib.h> //包含qsort的头文件
//比较函数
int Cmp(const void *pa, const void *pb)
{
return *(int*)pa > *(int*)pb;
}
int main(){
int n;
int arr[10000];
//输入数据
while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//使用qsort排序算法
qsort(arr, n, sizeof(int), Cmp);
//输出数据
for (i=0; i<n; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
return 0;
}
发表于 2018-02-08 16:27:05
回复(0)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 102;
int num[maxn] = {0};
int main()
{
int n;
while(cin >> n)
{
for(int i = 0; i < n; ++i)
{
cin >> num[i];
}
sort(num, num+n);
for(int i = 0; i < n; ++i)
{
cout << num[i] << " ";
}
cout << endl;
}
return 0;
}
发表于 2016-08-07 10:18:09
回复(0)
#include <stdio.h>
#include <algorithm>
for(int i=0;i<n;++i)
{
for(int j=0;j<n-i-1;++j)
{
if(buf[j]>buf[j+1])
{
tmp=buf[j+1];
buf[j+1]=buf[j];
buf[j]=tmp;
}
}
{
if(low>=high)return;
int pivot=a[low],l=low,h=high;
while(l<h)
{
while(l<h&&pivot<=a[h])
--h;
a[l]=a[h];
while(l<h&&pivot>=a[l])
++l;
a[h]=a[l];
}
a[l]=pivot;
qsort(a,low,l-1);
qsort(a,l+1,high);
}
int main()
{
int n;
int buf[100];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;++i)
{
scanf("%d",&buf[i]);
}
printf("%d ",buf[i]);
printf("\n");
}
return 0;
#include <algorithm>
using namespace std;
void bubblesort(int buf [],int n){
int tmp;for(int i=0;i<n;++i)
{
for(int j=0;j<n-i-1;++j)
{
if(buf[j]>buf[j+1])
{
tmp=buf[j+1];
buf[j+1]=buf[j];
buf[j]=tmp;
}
}
}
return;
}
void selectsort(int buf [],int n){
int m=0,t;
for(int i=0;i<n;++i)
{
m=n-i-1;
for(int j=0;j<n-i;++j)
{
if(buf[j]>buf[m])
{
m=j;
}
}
t=buf[n-1-i];
buf[n-1-i]=buf[m];
buf[m]=t;
}
return;
for(int i=0;i<n;++i)
{
m=n-i-1;
for(int j=0;j<n-i;++j)
{
if(buf[j]>buf[m])
{
m=j;
}
}
t=buf[n-1-i];
buf[n-1-i]=buf[m];
buf[m]=t;
}
return;
}
void qsort(int a[],int low,int high){
if(low>=high)return;
int pivot=a[low],l=low,h=high;
while(l<h)
{
while(l<h&&pivot<=a[h])
--h;
a[l]=a[h];
while(l<h&&pivot>=a[l])
++l;
a[h]=a[l];
}
a[l]=pivot;
qsort(a,low,l-1);
qsort(a,l+1,high);
}
int main()
{
int n;
int buf[100];
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;++i)
{
scanf("%d",&buf[i]);
}
//sort(buf,buf+n);内置快排函数
//bubblesort(buf,n);冒泡排序
//selectsort(buf,n);选择排序
qsort(buf,0,n-1);手动快排函数
for(int i=0;i<n;++i)printf("%d ",buf[i]);
printf("\n");
}
return 0;
}
效率：
冒泡 3ms 384k ...
选择 3ms 372k ...
手动快排 2ms 376k；3ms 384k；...
自动快排 3ms 364k；3ms 384k；...
测试用例不同 效率会有些许变化
发表于 2018-01-06 17:00:18
回复(1)
学到四种排序，开心
1.冒泡排序
#include<bits/stdc++.h> //万能头
using namespace std;
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> m[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (m[j] > m[j + 1]) {
int temp = m[j];
m[j] = m[j + 1];
m[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << m[i] << " ";
}
}
return 0;
} 2.选择排序
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> m[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i] > m[j]) {
int temp = m[i];
m[i] = m[j];
m[j] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << m[i] << " ";
}
}
return 0;
}
3.内置sort函数 #include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int m[100];
while(cin>>n){
for(int i=0;i<n;i++){
cin>>m[i];
}
sort(m,m+n); //需要调用#include<algorithm>
for(int i=0;i<n;i++){
cout<<m[i]<<" ";
}
}
return 0;
} 4.手动快速排序qsort函数 #include<bits/stdc++.h>
using namespace std;
int cmp(const void*a,const void*b) {
return *(int*)a - *(int*)b;//升序
//return *(int*)a - *(int*)b;//降序
}
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i<n; i++) {
cin >> m[i];
}
qsort(m, n,sizeof (m[0]),cmp);//需要调用#include<algorithm>
for (int i = 0; i<n; i++) {
cout << m[i] << " ";
}
}
return 0;
}
发表于 2020-02-17 17:17:37
回复(1)
//选择排序+冒泡排序
#include <iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
int i,j,a[100];
for(i=0;i<n;i++)
cin>>a[i];
//选择排序
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]>a[j]){
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
//冒泡排序
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
//或者用C++自带的排序函数
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
while(cin>>n){
int i,j,a[100];
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
编辑于 2017-12-04 10:57:52
回复(0)
写了好几种排序，练一练
#include <iostream>
#include <vector>
using namespace std;
//int* simple_swap_sort(int *a,int n); //简单的交换排序
//int* bubble_sort(int* a,int n); //冒泡排序
//int* simple_select_sort(int *a,int n); //简单的选择排序
//int* simple_insert_sort(int *a,int n); //简单的插入排序
//int* shell_sort(int *a,int n); //希尔排序
//int* merge_sort(int *a,int n); //归并排序配合合并函数使用 ps:这递归写的好烂
//int* merge(int *a,int *b,int a_n,int b_n);
int* quick_sort(int *a,int n); //快速排序
void Print(int a[],int n); //输出函数
int main(){
int n,value;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++){
cin>>value;
arr[i]=value;
}
Print(quick_sort(arr,n),n);
// Print(merge_sort(arr,n),n);
// Print(shell_sort(arr,n),n);
// Print(simple_insert_sort(arr,n),n);
// Print(simple_swap_sort(arr,n),n);
// Print(simple_select_sort(arr,n),n);
// Print(bubble_sort(arr,n),n);
delete []arr;
return 0;
}
int* quick_sort(int *a,int n){
if(n<1)
return a;
int i=0,j=n-1;
int temp=*a,change;
while(i<j){
while(*(a+j)>=temp&&i<j){
--j;
}
while(*(a+i)<=temp&&i<j){
++i;
}
if(i<j){
change=*(a+i);
*(a+i)=*(a+j);
*(a+j)=change;
}
}
*a=*(a+i);
*(a+i)=temp;
quick_sort(a,i);
quick_sort(a+i+1,n-i-1);
return a;
}
//int* merge(int *a,int *b,int a_n,int b_n){
// int i=0,j=0,n=0,len=a_n+b_n;
// int* result=new int[len];
// while(i<a_n&&j<b_n){
// if(a[i]<b[j]){
// result[n]=a[i];
// ++i;
// ++n;
// }else{
// result[n]=b[j];
// ++j;
// ++n;
// }
// }
// while(i<a_n){
// result[n]=a[i];
// ++i;
// ++n;
// }
// while(j<b_n){
// result[n]=b[j];
// ++j;
// ++n;
// }
// for(int i=0;i<len;++i){
// *(a+i)=result[i];
// }
// delete[] result;
// return a;
//}
//int* merge_sort(int *a,int n){
// if(n<2){
// return a;
// }
// int *right=a;
// int *left=a+n/2;
// merge_sort(right,n/2);
// merge_sort(left,n-n/2);
// merge(right,left,n/2,n-n/2);
// return a;
//}
//int* shell_sort(int *a,int n){
// int k,temp;
// for(int gap=n/2;gap>0;gap/=2){
// for(int i=0;i<gap;++i){
// for(int j=i;j<n;j+=gap){ //内层是插入排序
// temp=*(a+j);
// for(k=j;(k>i)&&(*(a+k-gap)>temp);k-=gap){
// *(a+k)=*(a+k-gap);
// }
// *(a+k)=temp;
// }
// }
// }
// return a;
//}
//int* simple_insert_sort(int *a,int n){
// int temp,k;
// for(int i=1;i<n;++i){
// temp=*(a+i);
// for(k=i;(*(a+k-1)>temp)&&(k>0);--k){
// *(a+k)=*(a+k-1);
// }
// *(a+k)=temp;
// }
// return a;
//}
//int* simple_select_sort(int *a,int n){
// int temp,min;
// for(int i=0;i<n;++i){
// min=i;
// for(int j=i;j<n;++j){
// if(*(a+min)>*(a+j)){
// min=j;
// }
// }
// temp=*(a+i);
// *(a+i)=*(a+min);
// *(a+min)=temp;
// }
// return a;
//}
//int* bubble_sort(int* a,int n){
// int temp;
// for(int i=0;i<n;++i){
// int flag=0;
// for(int j=0;j<n-i-1;++j){
// if(*(a+j)>*(a+j+1)){
// temp=*(a+j);
// *(a+j)=*(a+j+1);
// *(a+j+1)=temp;
// ++flag;
// }
// }
// if(!flag)
// break;
// }
// return a;
//}
//int* simple_swap_sort(int *a,int n){
// int temp;
// for(int i=0;i<n;++i){
// for(int j=i;j<n;++j){
// if(*(a+i)>*(a+j)){
// temp=*(a+j);
// *(a+j)=*(a+i);
// *(a+i)=temp;
// }
// }
// }
// return a;
//}
void Print(int a[],int n){
for(int i=0;i<n;++i){
cout<<a[i]<<' ';
}
cout<<endl;
}
编辑于 2020-03-09 12:41:30
回复(0)
/** * 快速排序 * 第一记录为枢轴 * @param a 需要排序的数组 * @param low 数组的起始下标 * @param high 数组的末尾下标 */public static void QSort(int a[], int low, int high) { if(low >= high) return; int pivot = a[low], l = low, h = high; for(; l < h; ) { for(; l < h && a[h] >= pivot; h--); a[l] = a[h]; for(; l < h && a[l] <= pivot; l++); a[h] = a[l]; } a[l] = pivot; QSort(a, low, l - 1); QSort(a, l + 1, high); }
编辑于 2016-06-27 22:13:12
回复(2)
//冒泡排序
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int arr[10000]={};
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j+1]<arr[j]){
int temp;
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;}
}}
for(int i=0;i<n;i++){
printf("%d ",arr[i]);}
return 0;}
//选择排序
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int arr[10000]={};
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}int k;
for(int i=0;i<n;i++){
k=i;
for(int j=i+1;j<n;j++){
if(arr[k]>arr[j])k=j;
}
if(k!=i){
int temp;
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
for(int i=0;i<n;i++){
printf("%d ",arr[i]);}
return 0;}
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int arr[10000]={};
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j+1]<arr[j]){
int temp;
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;}
}}
for(int i=0;i<n;i++){
printf("%d ",arr[i]);}
return 0;}
//选择排序
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int arr[10000]={};
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}int k;
for(int i=0;i<n;i++){
k=i;
for(int j=i+1;j<n;j++){
if(arr[k]>arr[j])k=j;
}
if(k!=i){
int temp;
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
for(int i=0;i<n;i++){
printf("%d ",arr[i]);}
return 0;}
编辑于 2022-11-12 22:12:02
回复(0)
//所有基本的排序方法了，桶排序、基数排序暂不写了
#include<iostream>
using namespace std;
const int N = 110, MAX = 1e5;
int a[N];
int n;
int h[N], idx;//heap_sort用
int tmp[N];//merge_sort用
int bkt[MAX];//counting_sort用
void buble_sort(){
for(int i = 0; i < n - 1; i ++)
for(int j = 0; j < n - 1 - i; j ++){
if(a[j]>a[j+1]) swap(a[j], a[j + 1]);
}
}
void quick_sort(int l, int r){
if(l>=r) return;
int x = a[(l + r) / 2];
int i = l - 1, j = r + 1;
while(i<j){
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
quick_sort(l, j);
quick_sort(j+1, r);
}
void selection_sort(){
for(int i = 0; i < n - 1;i ++){
int min_pos = i;
for(int j = i + 1; j < n; j ++)
if(a[j]<a[min_pos]) min_pos = j;
swap(a[i], a[min_pos]);
}
}
void down(int u){
int t = u;
if(u*2<=idx&&h[u*2]<h[t]) t = u*2;
if(u*2+1<=idx&&h[u*2+1]<h[t]) t= u*2+1;
if(t!=u){
swap(h[t], h[u]);
down(t);
}
}
void heap_sort(){
for(int i = 1; i <= n; i ++) h[i] = a[i-1];
idx = n;
for(int i = idx/2; i > 0; i --) down(i);
for(int i = 0; i < n; i ++){
a[i] = h[1];
h[1] = h[idx--];
down(1);
}
}
void insertion_sort(){
for(int i = 1; i < n; i ++){
int cur_idx = a[i];
int j;
for(j = i-1; j >=0 && a[j]>cur_idx; j --){
a[j+1] = a[j];
}
a[j+1] = cur_idx;
}
}
void binary_insertion_sort(){
for(int i = 1; i < n; i ++){
int cur_idx = a[i];
int l = 0, r = i - 1;
while(l<r){
int mid = (l + r + 1) / 2;
if(a[mid]<=cur_idx) l = mid;
else r = mid - 1;
}
if(a[l]>cur_idx) l = -1;
int j;
for(j = i - 1; j>l ;j --) a[j+1] = a[j];
a[j+1] = cur_idx;
}
}
void shell_sort(){
for(int gap = n/2; gap>=1; gap /= 2){
for(int i = gap; i < n; i ++){
int cur_idx = a[i];
int j;
for(j = i - gap; j>=0 && a[j]>cur_idx; j -= gap){
a[j+gap] = a[j];
}
a[j + gap] = cur_idx;
}
}
}
void merge_sort(int l, int r){
if(l>=r) return;
int mid = (l + r) / 2;
merge_sort(l, mid), merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while(i<=mid) tmp[k++] = a[i++];
while(j<=r) tmp[k++] = a[j++];
for(int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];
}
void counting_sort(){
int max = 0;
for(int i = 0 ; i < n; i ++){
bkt[a[i]]++;
if(a[i]>max) max = a[i];
}
int j = 0;
for(int i = 0; i < max+1; i ++){
while(bkt[i]){
a[j++] = i;
bkt[i]--;
}
}
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
// buble_sort();
// quick_sort(0, n - 1);
// selection_sort();
// heap_sort();
// insertion_sort();
// binary_insertion_sort();
// shell_sort();
merge_sort(0, n - 1);
for(int i = 0; i < n; i ++) printf("%d ", a[i]);
return 0;
}
发表于 2021-07-05 18:34:19
回复(0)
问题信息
难度：
136条回答
129收藏
22332浏览
通过挑战的用户
查看代码-
2023-03-14 15:41:40
-
2023-03-14 10:51:08
-
2023-03-13 23:03:17 -
2023-03-12 15:15:46
-
2023-03-12 12:50:40
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
