目的：给出一组实验来比较排序算法的时间性能 要求： （1）时间性能 （2）实验数据应具有说服力 （3）实验结果要能以清晰的形式给出，如图、表等。 （4）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （5）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 （6）要给出实验的方案及其分析。
软件环境：visual stdio 2017 硬件环境：①CPU：Intel（R）Core（TM）i7-8565U CPU @1.80Ghz ②内存：8.0GB
给出一组实验来比较排序算法的时间性能
选取若干个排序算法，对每种算法进行大量数据测试，同一规模的数据进行3次测试取平均值，最终得到若干个实验数据，进行绘图展示。
本次实验选取直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序，归并排序这7种算法。 分为2个大实验组，第一个大实验组为算法时间复杂度为O（n²）的算法，其中有直接插入排序，冒泡排序，直接选择排序。 第二个实验组为算法时间复杂度为O（nlogn）的算法，其中有希尔排序，快速排序，堆排序，归并排序。 4.3 详细设计 在第一个实验组中，选取规模分别为1000,5000,10000,50000,75000,100000,125000,175000,200000,250000的数据，每种数据测试三次取平均值。 在第二个实验组中，选取规模分别为10000,100000,200000,250000,500000,600000,750000,900000,1000000,10000000,25000000,30000000,40000000,50000000,60000000,75000000,100000000的数据，每种数据测试三次取平均值。在这些数据中，以1000000为分界点，分别制图。 制图采用python中的matplotlib工具，制作曲线图。
直接插入排序 template<typename T> void insert_sort(T array[], int n) { for (int i = 1; i < n; i++) { T temp = array[i]; int j = i - 1; while (array[j] > temp&&j >= 0) array[j + 1] = array[j--]; array[j + 1] = temp; } } 希尔排序 template<typename T> void shell_sort(T array[], int n) { int d = n / 2; while (d > 0) { for (int i = d; i < n; i++) { T temp = array[i]; int j = i - d; while (j >= 0 && temp < array[j]) { array[j + d] = array[j]; j -= d; } array[j + d] = temp; } d = d / 2; } } 冒泡排序 template<typename T> void bubble_sort(T array[],int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (array[j] > array[j + 1]) { T temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } } 快速排序 template<typename T> void quick_sort(T array[], int left, int right) { if (left >= right) return; int i = left, j = right; T temp = array[left]; while (i != j) { while (array[j] > temp&&j > i) j--; if (i < j) array[i++] = array[j]; while (array[i] < temp&&i < j) i++; if (i < j) array[j--] = array[i]; } array[i] = temp; quick_sort(array, i + 1, right); quick_sort(array, left, i - 1); } 直接选择排序 template<typename T> void select_sort(T array[],int n) { for (int i = 0; i < n - 1; i++) { int index = i; for (int j = i + 1; j < n; j++) { if (array[j] < array[index]) index = j; } if (i != index) { T temp = array[i]; array[i] = array[index]; array[index] = temp; } } } 归并排序 template<typename T> void merge_sort(T array[], int left, int right) { if (left >= right) return; int mid = (left + right) / 2; merge_sort(array, left, mid); merge_sort(array, mid + 1, right); int i = left, k = left, j = mid + 1; while (i <= mid&&j <= right) { if (array[i] < array[j]) assist[k++] = array[i++]; else assist[k++] = array[j++]; } while (i <= mid) assist[k++] = array[i++]; while (j <= right) assist[k++] = array[j++]; for (int k = left; k <= right; k++) array[k] = assist[k]; } 堆排序 template<typename T> void swap(T arr[], int a, int b) { T temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } template<typename T> void adjustHeap(T arr[], int i, int length) { T temp = arr[i]; for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { if (k + 1 < length&&arr[k] < arr[k + 1]) k++; if (arr[k] > temp) { arr[i] = arr[k]; i = k; } else break; } arr[i] = temp; } template<typename T> void heap_sort(T arr[], int length) { for (int i = length / 2 - 1; i >= 0; i--) adjustHeap(arr, i, length); for (int j = length - 1; j > 0; j--) { swap(arr, 0, j); adjustHeap(arr, 0, j); } }数据规模详见上述分析，具体数据由随机数产生，范围为0~1073283121（ rand()*rand() ）。
分析： 在图像中可以清晰地看出每种算法的时间复杂度。 先进行纵向对比，可以发现三种O（n²）的算法在数据规模达到250000时的排序用时便已全部超过20s，而O（nlogn）的算法在数据规模达到40000000时的排序用时才开始出现超过20s的现象，二者差异巨大。
故：时间复杂度为O（nlogn）的算法的时间性能远远大于O（n²）时间复杂度算法的时间性能。
再进行横向对比，可以发现：时间复杂度为O（n²）的算法中，各算法对相同规模的数据的排序时间有T（冒泡排序）＞T（选择排序）＞T（插入排序），时间复杂度为O（nlogn）的算法中，各算法对相同规模的数据的排序时间有T（希尔排序）＞T（堆排序）＞T（归并排序）＞T（快速排序） 故：相同时间复杂度的算法在进行相同规模数据排序时，是有差异的，这种差异随着数据规模的增加愈发明显。在O（n²）的算法中，插入排序优于选择排序，选择排序优于冒泡排序；在O（nlogn）的算法中，快速排序优于归并排序，归并排序优于堆排序，堆排序优于希尔排序。
在本次实验中，我通过数据，清晰地认识到了不同时间复杂度的算法在处理大规模数据时的差异，同时也认识到，时间复杂度是相对的，尽管时间复杂度的等级相同，但在运行时所耗费的时间也会有差异。本次实验启示我以后在解决问题设计算法的时候，不仅要考虑时间复杂度的等级，也需要关注实际语句的执行次数，对其优化，达到最优。
