8種排序算法比較

8種排序算法，各算法名稱見下表或見源碼。運行程序時，將需要你輸入一數值，以確定對多少隨機數進行排序。然后將會顯示各排序算法的耗時。并且你可選擇時否進行正序和反序測試。

由于水平有限，可能存在一些錯誤，還請各位多多指點！

通過實驗我們可將結果列入下表。

以下是VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G)

因為在多任務操作系統下，系統將進行進程序調度，影響實驗結果。以下是經過稍微修正過的值。如果要取得更準確的值，我們得多次實驗求其平均值。

排序算法實驗比較(單位：秒)

n 方法	1K	10K	100K	200K	100K
					正序	逆序
冒泡排序	0	0.422	44.790	188.462	0	31.459
冒泡排序2	0	0.281	30.335	131.771	0	27.568
快速排序	0	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	0	24.865
Shell排序	0	0	0.047	0.110	0.015	0.015
歸并排序	0	0	0.031	0.094	0.032	0.032
基數排序	0	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))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字符串這樣能分解，若是浮點型那就不行了。

按平均時間將排序分為類：

?

(1)?平方階(O(n²))排序
　　各類簡單排序，例如直接插入、直接選擇和冒泡排序；

?

(2)?線性對數階(O(nlog2n))排序
　　如快速排序、堆排序和歸并排序；

?

(3)?O(n^1+§))排序
　　§是介于0和1之間的常數。希爾排序便是一種；

?

(4)?線性階(O(n))排序
　　本程序中的基數排序，此外還有桶、箱排序。

排序方法的選擇

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法很重要
(1)若n較小，可采用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好，它會比選擇更少的比較次數；
但當記錄規模較大時，因為直接選擇移動的記錄數少于直接插人，所以宜用選直接選擇排序。
這兩種都是穩定排序算法。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜(這里的隨機是指基準取值的隨機，原因見上的快速排序分析)；這里快速排序算法將不穩定。
(3)若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
快速排序是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序雖不會出現快速排序可能出現的最壞情況。但它需要建堆的過程。這兩種排序都是不穩定的。
　?歸并排序是穩定的排序算法，但它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。
(4)特殊的箱排序、基數排序
它們都是一種穩定的排序算法，但有一定的局限性：
　　1、關鍵字可分解。
　　2、記錄的關鍵字位數較少，如果密集更好
　　3、如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。

trackback:?http://blog.csdn.net/ctang/article/details/37914