给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
- 数据1：只有1个元素；
- 数据2：11个不相同的整数，测试基本正确性；
- 数据3：103个随机整数；
- 数据4：104个随机整数；
- 数据5：105个随机整数；
- 数据6：105个顺序整数；
- 数据7：105个逆序整数；
- 数据8：105个基本有序的整数；
- 数据9：105个随机正整数，每个数字不超过1000。
输入格式:
输入第一行给出正整数N（≤105），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。
输出格式:
在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。
输入样例:
11 4 981 10 -17 0 -20 29 50 8 43 -5输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981#include<cstdio> #include<cstdlib> const int maxn = 100010; //插入排序 void insertion_sort(int arr[],int n); //希尔排序 void shell_sort(int arr[],int n); void sedgewick_sort(int arr[], int n); //选择排序 void select_sort(int arr[], int n); //最小堆排序 void percdown(int arr[], int n, int i); void heap_sort(int arr[], int n); //冒泡排序 void bubble(int arr[], int n); //快速排序 void quick(int arr[], int n); void quick_sort(int arr[], int low, int high); int partition(int arr[], int low, int high); //归并排序-循环方式 void merge_sort_loop(int arr[], int n); void msort_loop(int arr[], int low, int high); void merge_loop(int arr[], int low, int mid, int high); //归并排序--递归方式 void merge_sort_recursive(int arr[], int n); void msort_recursive(int arr[], int tmp[], int low, int high); void merge_recursive(int arr[], int tmp[], int low, int mid, int high); int main() { int n; int arr[maxn]; scanf("%d",&n); for (int i = 0; i < n; i++) { scanf("%d",&arr[i]); } //Insertion_sort(arr, n); //shell_sort(arr, n); //sedgewick_sort(arr, n); //select_sort(arr, n); //heap_sort(arr, n); //bubble(arr, n); //quick(arr, n); //merge_sort_loop(arr, n); merge_sort_recursive(arr, n); for (int i = 0; i < n; i++) { printf("%d",arr[i]); if (i < n - 1) { printf(" "); } } return 0; } void insertion_sort(int arr[],int n) { for (int i = 0; i < n; i++) { int j = i; int tmp = arr[i]; for (; j > 0 && arr[j - 1] > tmp; j--) { arr[j] = arr[j - 1]; } arr[j] = tmp; } } void shell_sort(int arr[],int n) { for (int d = n/2; d > 0; d /= 2) { for (int i = d; i < n; i++) { int tmp = arr[i]; int j = i; for (; j >= d && arr[j - d] > tmp; j -= d) { arr[j] = arr[j - d]; } arr[j] = tmp; } } } void sedgewick_sort(int arr[], int n) { int si = 0; int sedgewick[] = {929, 505, 209, 103, 41, 19, 5, 1, 0}; for (; sedgewick[si] >= n; si++) { ; } for (; sedgewick[si] > 0; si++) { int d = sedgewick[si]; for (int i = d; i < n; i++) { int tmp = arr[i]; int j = i; for (; j >= d && arr[j - d] > tmp; j -= d) { arr[j] = arr[j - d]; } arr[j] = tmp; } } } void select_sort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int tmp = arr[i]; int t = i; for (int j = i + 1; j < n; j++) { if (arr[j] < tmp) { tmp = arr[j]; t = j; } } arr[t] = arr[i]; arr[i] = tmp; } } void heap_sort(int arr[], int n) { for (int i = (n-2)/2; i >= 0; i--) { percdown(arr, n, i); } for (int i = n - 1; i > 0; i--) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; percdown(arr, i, 0); } } void percdown(int arr[], int n, int i) { int parent = i; int child; int x = arr[parent]; for (; parent * 2 + 1 < n; parent = child) { child = parent * 2 + 1; if (child < n - 1 && arr[child+1] > arr[child]) { child++; } if (x > arr[child]) { break; } else { arr[parent] = arr[child]; } } arr[parent] = x; } void bubble(int arr[], int n) { bool swap = true; while (swap) { swap = false; for (int i = 0; i < n-1; i++) { if (arr[i] > arr[i+1]) { arr[i] += arr[i+1]; arr[i+1] = arr[i] - arr[i+1]; arr[i] -= arr[i+1]; swap = true; } } } } void quick(int arr[], int n) { quick_sort(arr, 0, n-1); } void quick_sort(int arr[], int low, int high) { if(low < high) { int pivotpos = partition(arr,low,high); quick_sort(arr,low,pivotpos-1); quick_sort(arr,pivotpos+1,high); } } int partition(int arr[], int low, int high) { int tmp = arr[low]; while(low < high) { while(low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; while(low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; } arr[low] = tmp; return low; } void merge_sort_loop(int arr[], int n) { msort_loop(arr, 0, n-1); } void msort_loop(int arr[], int low, int high) { if (low < high) { int mid = (low + high) / 2; msort_loop(arr, low, mid); msort_loop(arr, mid + 1, high); merge_loop(arr, low, mid, high); } } void merge_loop(int arr[], int low, int mid, int high) { int i,j,k; int len_left = mid - low + 1; int len_right = high - mid ; int L[len_left]; int R[len_right]; for (i = 0 ; i < len_left; i++) { L[i] = arr[low + i]; } for (i = 0; i < len_right; i++) { R[i] = arr[1 + mid + i]; } i = 0; j = 0; k = low; while(i < len_left && j < len_right) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while(i < len_left) { arr[k++] = L[i++]; } while (j < len_right) { arr[k++] = R[j++]; } } void merge_sort_recursive(int arr[], int n) { int* tmp = (int *)malloc(n * sizeof(int)); msort_recursive(arr, tmp, 0, n-1); free(tmp); } void msort_recursive(int arr[], int tmp[], int low, int high) { if (low < high) { int mid = (low + high) / 2; msort_recursive(arr, tmp, low, mid); msort_recursive(arr, tmp, mid+1, high); merge_recursive(arr, tmp, low, mid, high); } } void merge_recursive(int arr[], int tmp[], int low, int mid, int high) { int left = low; int right = mid + 1; int start = low; while (left <= mid && right <= high) { if (arr[left] <= arr[right]) { tmp[start++] = arr[left++]; } else { tmp[start++] = arr[right++]; } } while (left <= mid) { tmp[start++] = arr[left++]; } while(right <= high) { tmp[start++] = arr[right++]; } for (; low <= high; low++) { arr[low] = tmp[low]; } }