一、/冒泡排序/ 平均时间复杂度:0(n^2) 运行时间:1000随机数：时间为0.003s 1万随机数：时间为0.57s 10万随机数：时间为40.224s void BubbleSort(int arr[], int length) { for (int i = 0; i < length; i++) { for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp; temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } 二、/* 选择排序 / 平均时间复杂度:0(n^2) 运行时间:1000随机数：时间为：0.004s 1万随机数：时间为：0.225s 10万随机数：时间为：34.125s void SelectionSort(int arr[], int length) { int index, temp; for (int i = 0; i < length; i++) { index = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[index]) index = j; } if (index != i) { temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } } 三、/插入排序/ 平均时间复杂度：0(n^2) 运行时间:1000个随机数：时间为：0.003s 1万个随机数：时间为：0.195s 10万个随机数：时间为：21.671s void InsertSort(int arr[], int length) { for (int i = 1; i < length; i++) { int j; if (arr[i] < arr[i - 1]) { int temp = arr[i]; for (j = i - 1; j >= 0 && temp < arr[j]; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } } } 四、/归并排序/ 平均时间复杂度：0(nlog2n) 运行时间:1000随机数：时间为0.001s 1万随机数：时间为0.049s 10万随机数：时间为6.908s void MergeSort(int arr[], int start, int end, int * temp) { if (start >= end) return; int mid = (start + end) / 2; MergeSort(arr, start, mid, temp); MergeSort(arr, mid + 1, end, temp); int length = 0; int i_start = start; int i_end = mid; int j_start = mid + 1; int j_end = end; while (i_start <= i_end && j_start <= j_end) { if (arr[i_start] < arr[j_start]) { temp[length] = arr[i_start]; length++; i_start++; } else { temp[length] = arr[j_start]; length++; j_start++; } } while (i_start <= i_end) { temp[length] = arr[i_start]; i_start++; length++; } while (j_start <= j_end) { temp[length] = arr[j_start]; length++; j_start++; } for (int i = 0; i < length; i++) { arr[start + i] = temp[i]; } } 五、/快速排序/ 平均时间复杂度：0(n*log2n) 运行速度:1000随机数：时间为0.001s 1万随机数：时间为0.005s 10万随机数：时间为0.139s void QuickSort(int arr[], int start, int end) { if (start >= end) return; int i = start; int j = end; int baseval = arr[start]; while (i < j) { while (i < j && arr[j] >= baseval) { j--; } if (i < j) { arr[i] = arr[j]; i++; } while (i < j && arr[i] < baseval) { i++; } if (i < j) { arr[j] = arr[i]; j--; } } arr[i] = baseval; QuickSort(arr, start, i - 1); QuickSort(arr, i + 1, end); } 六、/希尔排序/ 平均时间复杂度：0(n^1.3) 运行速度:1000随机数：时间为：0.001s 1万随机数：时间为：0.051s 10万随机数：时间为：5.253s void ShellSort(int arr[], int length) { int increasement = length; int i, j, k; do { increasement = increasement / 3 + 1; for (i = 0; i < increasement; i++) { for (j = i + increasement; j < length; j += increasement) { if (arr[j] < arr[j - increasement]) { int temp = arr[j]; for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement) { arr[k + increasement] = arr[k]; } arr[k + increasement] = temp; } } } } while (increasement > 1); } 比较总结： 1.对1000个随机数进行排序： 六种排序算法的所需时间均接近0.001s，速度都很快。 2.对1万个随机数进行排序： 快速0.005s < 希尔0.051s < 归并0.049s < 插入0.195s < 选择0.225s < 冒泡0.57s 很明显，快速排序法最快，冒泡排序法最慢。 3.对10万个随机数进行排序： 快速0.139s < 希尔5.253s < 归并6.908s < 插入21.671s < 选择34.125s < 冒泡40.224s 快速排序法最快，冒泡排序法最慢。 4.对100万个随机数进行排序： 快速10.624s，其余算法时间未知，几分钟内排序无法完成。