最近在PTA练习题目时，发现了这道非常好的题目。推荐这道题的理由是：这道题给出了最大十万个数据，因此可以直观地看出各个排序方法的时间好坏（时间复杂度 & 空间复杂度）。
希望各位在看的时候，不妨自己手底下试试，毕竟实践出真知嘛
好，我们来看题目——
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。 本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；数据2：11个不相同的整数，测试基本正确性；数据3：103个随机整数；数据4：104个随机整数；数据5：105个随机整数；数据6：105个顺序整数；数据7：105个逆序整数；数据8：105个基本有序的整数；数据9：105个随机正整数，每个数字不超过1000。 我在此给出了10种算法，其中冒泡我用了两种方法（后来回顾的时候感觉这两种方法其实是一样的……），基数排序等我后面补充（O(∩_∩)O哈哈~）。10月15号更新：基数排序
#include <stdio.h> #include <stdlib.h> #include <limits.h> void sort_method_11(int *arr, int len) { int max = INT_MIN; for (int i=0; i<len; i++) { //找序列中的最大值 if (arr[i] > max) max = arr[i]; } int maxlenth = 0; while (max > 0) { //算出最大数字的位数 max /= 10; maxlenth++; } int restore[20][len]; //创建二维数组，二维数组有10列，每一列存放对应数字 static int count[20]; int i, n; for (i=0, n=1; i<maxlenth; i++, n*=10) { for (int j=0; j<len; j++) { int remainder = arr[j] / n % 10 + 9; //+9是为了让数字能在正数范围内 restore[remainder][count[remainder]] = arr[j]; count[remainder]++; } int index = 0; for (int k=0; k<20; k++) { if (count[k] != 0) { for (int i=0; i<count[k]; i++) { arr[index] = restore[k][i]; index++; } count[k] = 0; } } } } int main(void) { int len; scanf("%d", &len); int arr[len]; for (int i=0; i<len; i++) { scanf("%d", &arr[i]); } sort_method_11(arr, len); for (int i=0; i<len; i++) { if (i == len-1) printf("%d", arr[i]); else printf("%d ", arr[i]); } printf("\n"); return 0; }以下是其他的算法—— 代码基于C语言，我先给出了各个函数的接口，main( )函数放在最后了
直接插入排序 //直接插入排序 void sort_method_1(int *arr, int len) { int i, j; int temp; for (i=1; i<len; i++) { if (arr[i] < arr[i-1]) { temp = arr[i]; for (j=i-1; j>=0; j--) { //必须要加限定长度的条件，否则会取到数组之外的内存 if (arr[j] <= temp) { break; } arr[j+1] = arr[j]; } arr[j+1] = temp; } } } 折半插入排序 //折半插入排序 void sort_method_2(int *arr, int len) { int low, high; int temp; for (int i=1; i<len; i++) { temp = arr[i]; low = 0; high = i - 1; while (low <= high) { //折半操作 int mid = (low + high) / 2; if (arr[mid] < temp) { low = mid + 1; }else { high = mid - 1; } } for (int j = i-1; j>high; j--) { //挪出插入位置 arr[j+1] = arr[j]; } arr[high+1] = temp; //插入新值 } } 2-路插入排序 //2-路插入排序（对大量数据(>100000)可能会超时） void sort_method_3(int *arr, int len) { int newArr[len]; int first, final; int i = 0; newArr[0] = arr[i]; first = final = 0; for (i=1; i<len; i++) { if (arr[i] > newArr[final]) { final = (final + 1 + len) % len; newArr[final] = arr[i]; }else if (arr[i] < newArr[first]) { first = (first - 1 + len) % len; newArr[first] = arr[i]; }else { int j; for (j=final; ; j=(j-1+len)%len) { if (newArr[j] <= arr[i]) { break; } newArr[(j+1+len)%len] = newArr[j]; } newArr[(j+1+len)%len] = arr[i]; final = (final + 1 + len) % len; } } int k, m; for (k=first, m=0; m<len; k=(k+len+1)%len, m++) { arr[m] = newArr[k]; } } 希尔排序 //希尔排序（我没想到希尔居然比快排快得多……） void Shell_for_one(int *arr, int len, int dk) { //一趟 int i, j; for (i=dk; i<len; i++) { if (arr[i] < arr[i-dk]) { int temp = arr[i]; for (j=i-dk; j>=0; j-=dk) { if (arr[j] <= temp) break; arr[j+dk] = arr[j]; } arr[j+dk] = temp; } } } void sort_method_4(int *arr, int len) { int dk = len / 2; while (dk >= 1) { Shell_for_one(arr, len, dk); dk /= 2; } } 冒泡排序（两种） //冒泡排序（数据量超过100000会超时） void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void sort_method_5(int *arr, int len) { //冒泡——方法1 int i, j; for (j=len-1; j>0; j--) { for (i=0; i<j; i++) { if (arr[i+1] < arr[i]) { swap(&arr[i+1], &arr[i]); } } } } void sort_method_6(int *arr, int len) { //冒泡——方法2 int i, j; for (i=1; i<len; i++) { for (j=0; j<len-i; j++) { if (arr[j+1] < arr[j]) { swap(&arr[j+1], &arr[j]); } } } } 快速排序 //快速排序（快排不是O(logn)吗，为啥这么慢，100000数据要3000多ms？？） int qsort_for_one(int *arr, int ptr_left, int ptr_right) { int pivot = arr[ptr_left]; while (ptr_left < ptr_right) { while (ptr_left < ptr_right && arr[ptr_right] >= pivot) { ptr_right--; } arr[ptr_left] = arr[ptr_right]; while (ptr_left < ptr_right && arr[ptr_left] <= pivot) { ptr_left++; } arr[ptr_right] = arr[ptr_left]; } arr[ptr_left] = pivot; return ptr_left; } void Quick_Sort(int *arr, int len, int low, int high) { if (low < high) { int mid = qsort_for_one(arr, low, high); Quick_Sort(arr, len, low, mid-1); Quick_Sort(arr, len, mid+1, high); } } void sort_method_7(int *arr, int len) { Quick_Sort(arr, len, 0, len-1); } 简单选择排序 //简单选择排序 int ChooseMin(int *arr, int start, int len) { int min = arr[start], min_pos = 0; for (int i=start; i<len; i++) { if (arr[i] < min) { min_pos = i; min = arr[i]; } } return min_pos; } void sort_method_8(int *arr, int len) { int tem_pos; for (int i=0; i<len-1; i++) { //到倒数第二个数 tem_pos = ChooseMin(arr, i, len); if (tem_pos != i) { swap(&arr[i], &arr[tem_pos]); } } } 堆排序 //堆排序（针对大数据，堆排速率特别快【哪怕是最坏情况也是O(logn)】） void Heap_Adjust(int *arr, int start, int end) { //建立大顶堆 int record = arr[start]; int i; for (i=start*2; i<=end; i*=2) { if (i<end && arr[i] < arr[i+1]) i++; if (record >= arr[i]) break; arr[start] = arr[i]; start = i; } arr[start] = record; } void sort_method_9(int *arr, int len) { for (int j=len/2; j>=0; j--) { Heap_Adjust(arr, j, len-1); } for (int i=len-1; i>=0; i--) { swap(&arr[0], &arr[i]); Heap_Adjust(arr, 0, i-1); } } 归并排序 //归并排序（这种方法针对大数据也很快，不到60ms即可得出结果） void Merge(int *arr, int *arr_new, int i, int m, int n) { //将两个有序小序列arr[i...m]和arr[m+1...n]归并为有序的大序列arr_new[i...n] //j指针指向后面那个数组，k指向新数组；i指针是第一个数组的指针 int j, k; for (j=m+1, k=i; i<=m && j<=n; k++) { if (arr[i] < arr[j]) { arr_new[k] = arr[i]; i++; }else { arr_new[k] = arr[j]; j++; } } while (i <= m) { arr_new[k++] = arr[i++]; } while (j <= n) { arr_new[k++] = arr[j++]; } } void interface(int *arr, int len, int *new_arr, int s, int t) { //s指数组头，t指数组尾 int newer_Arr[len]; //如果只有一个元素，无需归并 if (s == t) new_arr[s] = arr[s]; else { int m = (s+t) / 2; interface(arr, len, newer_Arr, s, m); //对左面递归 interface(arr, len, newer_Arr, m+1, t); //对右面递归 Merge(newer_Arr, new_arr, s, m, t); //整个进行一遍大排序 } } void sort_method_10(int *arr, int len) { interface(arr, len, arr, 0, len-1); }最后来看main( )函数
#include <stdio.h> int main(void) { int len; scanf("%d", &len); int arr[len]; for (int i=0; i<len; i++) { scanf("%d", &arr[i]); } sort_method_10(arr, len); for (int i=0; i<len; i++) { if (i == len-1) printf("%d", arr[i]); else printf("%d ", arr[i]); } printf("\n"); return 0; }