五、实验结果与分析
1、实验结：
实验数据结果汇总表：
CPU 内存 主板 AMD A6-3420M APU with Radeon(tm) HD Graphics 四核 姓名 李宇 7.48 GB 华硕 K53TK 学号 201131190310 班级 电信4班 电话 18825175417 email liandyu2008@163.com 操作系统 Windows 8 专业版 (Build 9200), 64-bit 编译软C-free 5.0 件 10^4 2*10^4 10^5 2*10^5 10^6 2*10^6 10^7 2*10^10^8 10^5 7 正序 逆序 24.87100.12500.C 4 58 3 直接插入 40.99(带监视哨） t(时间) 0.404 1.665 3 24.87100.12500.C 4 58 3 直接插入 40.46(无监视哨） t 0.388 1.586 8 49.99199.94999.冒泡（上C 05 85 94 升） 129.1t 1.255 5.088 45 49.99199.94999.C 04 6 78 128.6冒泡（下降） t 1.246 5.198 71 0.1700.3662.170 78 1618 42 快速（递归） 9995.6 166.432 9995.6 166.075 19999.9 517.741 19999.9 >5min >5min >5min 堆排序 (非递归) 二路归并 C t 选择排序 C 522.9 >5min 4.79625.8157.66320.8647.446 25 68 6 54 11.250.003 0.007 0.039 0.083 0.46 0.995 5.502 1 0.1230.2671.5663.33318.7139.43224.0468.068 361 51 .05 66 19 02 06 14.090.003 0.008 0.049 0.099 0.507 1.184 6.456 4 0.0290.0590.2990.599997 997 997 997 0 0 0 0 15.1033.630.004 0.01 0.069 0.137 0.947 2.189 8 4 0.0770.1681.0102.155 88 222.4t 63 >5min 9.71071.01167.91089.2471.C 04 87 31 57 38 28.8565.22希尔排序 t 0.005 0.014 0.109 0.244 1.82 4.243 4 4 当数据表容量为10^8时系统出现问题。 524 506 5 55.620.513 2.059 4 0.2660.6084.341711 676 5
2、实验分析 2.1直接插入排序 该算法虽然简单，但效率不高。由汇总表的数据可以看出，若初始数据为正序，总的关键字比较次数为最小，并且总的移动次数为0；若初始数据为逆序，总的比较次数达到最大值O（n2）；所以，算法对初始序列的敏感程度很大。 因为该算法的时间复杂度为O（n2），所以其对大规模的数据排序的效率很低，改进后的二分插入算法并没有改变总的比较次数，只是总的时间变小了，效率有所改进。
2.2冒泡排序 若初始数据为正序，则一趟扫描就可以完成排序，关键字的比较次数为n-1，没有移动次数，即在最好的情况下，冒泡排序的时间复杂度为O（n）；若初始数据为逆序，则比较次数和移动次数均达到最大值，最坏时间复杂度为O（n2）。 由汇总表可看出，该算法对于数据量大的排序的效率是很低的，使用改进的双向冒泡法进行排序时，效率有所改进，但仍为O（n2）。
2.3 快速排序 由汇总表中的正序和逆序数据可以看出，该算法对基本有序的初始记录进行排序的效率是很低的，其对初始序列的敏感程度大。 快速排序的平均时间复杂度约为1.39nlog2n，而且在所有排序方法当中的速度是最快的，尤其是在处理大规模无序数据时，其优势更为明显。
2.4二路归并 由汇总表可以看出，算法对初始序列的敏感程度很小，它的时间复杂度是O（nlog2n），它在较大数据排序时，性能不亚于快排，堆排，并且和初始数据顺序性无关，是一种稳定的排序算法，缺点就是它的空间复杂度，达到O（n）。
2.5堆排序 从汇总表可以看出，算法对初始序列的敏感程度很小。
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，堆排序的最坏时间复杂度为O(nlogn)，平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1），它是不稳定的排序方法。
2.6选择排序 从汇总表可以看出，算法对初始序列的敏感程度很小，该算法的时间复杂度为O（n2），该算法的优点在于记录的移动次数较少，当记录本身的数据量较大时，该算法比较有利，然而无论数据表的初始状态如何，在第i趟排序中选出最小（或最大）的记录，都需要做n-i次比较。 简单的改进算法二路选择排序，虽然时间复杂对仍为O（n2），但是由于扫描的趟数为n/2，算法的总执行时间大大减少。
2.7希尔排序 希尔排序的时间复杂度大约为O（n1.x），如O（n1.25）以下，可以看出O（n1.25）的增长速度也是较快的，大优于直接插入排序，然而，当数据量大时，该算法的效率也不理想了；由汇总表可看出，算法对初始序列的敏感程度很小。
六、结论
从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能为O(n2)不如堆排序和归并排序O(nlog2n)。而后两者相比较的结果是，在n较大时， 归并排序所需的时间较堆排序省，但它所需的辅助存储量最多。 快速排序，堆排序和希尔排序等时间性能较好的排序方法都是不稳定的，一般来说，排序过程中的比较是在相邻的两个记录关键字间进行的排序方法都是稳定的。由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行，则应根据问题所需慎重选择排序方法及其描叙算法。
综上所述，在这些排序方法中没有哪一中是绝对最优的，有的适用于n较大的情况，有的适用于n 较小的情况，因此，在实用时需要根据不同的情况适当选用，甚至可以将多种方法综合起来使用。
下面是一个总的表格，大致总结了我们常见的排序算法的特点。 排序法 冒泡 交换 选择 插入 希尔 快速 归并 堆
平均时间 O(n2) O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(nlogn) O(nlogn) 最差情形 O(n2) O(n2) O(n2) O(n2) O(ns) ，1