前几天应一个朋友的要求，帮他完成了数据排序的一个作业。觉得很有给大家参考的价值，所以经过他同意，作了些修改帖了上来。源代码见附件，代码中实现了8种排序算法，各算法名称见下表或见源码。运行程序时，将需要你输入一数值，以确定对多少随机数进行排序。然后将会显示各排序算法的耗时。并且你可选择时否进行正序和反序测试。 由于水平有限，可能存在一些错误，还请各位多多指点！ 通过实验我们可将结果列入下表。
以下是VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G)
因为在多任务操作系统下，系统将进行进程序调度，影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值，我们得多次实验求其平均值。
排序算法实验比较(单位：秒)
n 1K 10K 100K 方法 冒泡排序 冒泡排序2 快速排序 0 0.422 44.790 188.462 0 0.281 30.335 131.771 0 0 31.459 0 27.568 200K 100K 正序 逆序 0 0.016 0.047 5.095 7.002 直接选择排序 0 0.141 16.878 79.332 16.785 33.242 堆排序 0 0 0.031 0.109 0.031 0.015 直接插入排序 0 0.047 8.705 57.800 Shell排序 归并排序 基数排序 0 0 0 0 24.865 0 0.047 0.110 0.015 0.015 0 0.031 0.094 0.032 0.032 0 0.47 0.109 0.047 0.046 算法与结果联合分析
冒泡排序：在最优情况下只需要经过n- 1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最 后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。
冒泡排序２：它是冒泡排序的改良（一次下沉再一次上浮），最优情况和最坏情况与冒泡排序差不多，但是一般情况下它要好过冒泡排序，它一次下沉，再一次上浮，这样避免了因一个数的逆序，而造成巨大的比较。如（2,3,4,?, n-1,n,1），用冒泡排序需要n(n-1)/2次比较，而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次，第一轮1将上移一位，第二轮 1将移到首位，第三轮将发现无数据交换，序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法，只适合于数据基本有序的排序。
快速排序：它同样是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况
下，它的排序时间复杂度为Ｏ(nlog2n)。 即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是Ｏ(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正 序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排 序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法， 因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。
直接选择排序：简单的选择排序，它的比较次数一定：n(n -1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见 对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。
堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为Ｏ(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。
直接插入排序：简 单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值 移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。
希尔排序：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为１，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。
归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。