★ 基于“比較”操作的內部排序性能大PK

?

我們首先總結一下《排序結構專題1-4》中的十種方法的性能((N個關鍵字的待排序列))：

排序方法 ? ? ??

平均時間 ?

最壞時間??

輔助存儲空間

? 穩定性 ?

直接插入排序	O(N^2)?	O(N^2)??	O(1) ?? ? ? ??	? ? √ ?? ?
折半插入排序	O(N^2)	O(N^2)	O(1)	??? √
希爾排序	O(N*logN)	O(N*logN)	O(1)?	???? ×

起泡排序???????	O(N^2)	O(N^2)?????	O(1)??????????	? ? ? √ ? ?
快速排序	O(N*logN)	O(N^2)	O(logN)	????? ×

簡單選擇排序????	O(N^2)? ?? ???	O(N^2)???? ? ?	O(1) ? ? ?? ? ? ??	? ??? √?? ? ?
樹形選擇排序	O(N*logN)	O(N*logN)	O(N)	????? √
堆排序	O(N*logN)	O(N*logN)	O(1)	????? ×

歸并排序??? ? ? ? ? ? ?

O(N*logN)????? ?

O(N*logN)?? ???????

O(N) ?? ? ? ? ??????????????

√ ? ? ? ??

?

1、 O(N^2) 級別的普通排序算法，我們用 C++ 的隨機函數 rand() 產生的隨機數進行排序，并計算耗費時間。

其中分別隨機生成1W，3W，5W... 19W(增量為2W)共十組待排序列進行測試。得到直接插入排序、折半插入排序、起泡排序、簡單選擇排序的耗時統計圖如下所示(SPSS軟件做圖統計)。

?

?

從上圖可以發現，起泡排序的耗時最大，其他三者的耗時差不多。其中折半插入排序在待排數據量達到19W以后，其性能要比直接插入排序，和簡單排序要好一些。另外，在數據量較小的情況下，插入排序的性能要比選擇排序要略好。

?

普通算法分析：在數據規模較小時(9W之內)，折半插入、直接插入、簡單選擇插入差不多。當數據量較大時，折半插入要好一些。而起泡排序算法的時間代價是最昂貴的。 另外，普通排序算法基本上都是相鄰元素進行比較，因此O(N^2)基本的排序算法都是穩定的。

?

2、O(N*logN) 級別的先進排序算法，其時間復雜度要比普通算法要快得多。由于數據本身要小的多，因此我們沒有拿它們和普通算法進行比較，而是另外選擇從10W——140W(增量10W)的15組數據進行測試，耗時性能比較如下(SPSS軟件做圖統計)：

?

從上圖可以發現，先進排序的耗時代價遠遠小于普通排序算法。而先進算法之間也有區別。其中快速排序無疑是最優秀的。其次是歸并排序和希爾排序，堆排序稍微差一些，而最差的就是樹形選擇排序了。

?

先進算法分析：

(1) 就時間性能而言， 希爾排序、快速排序、樹形選擇排序、堆排序和歸并排序都是較為先進的排序方法。耗時遠小于O(N^2)級別的算法。

(2) 先進算法之中，快排的效率是最高的。 但其缺點十分明顯：在待排序列基本有序的情況下，會蛻化成起泡排序，時間復雜度接近 O(N^2)。

(3) 希爾排序的性能讓人有點意外，這種增量插入排序的高效性完全說明了：在基本有序序列中，直接插入排序絕對能達到令人吃驚的效率。但是希爾排序對增量的選擇標準依然沒有較為滿意的答案，要知道增量的選取直接影響排序的效率。

(4) 歸并排序的效率非常不錯，在數據規模較大的情況下，它比希爾排序和堆排序都要好。

(5)堆排序在數據規模較小的情況下還是表現不錯的，但是隨著規模的增大，時間代價也開始和上面兩種排序拉開的距離。

(6)樹形選擇排序并不是較好的先進排序方法，數據規模越大，其耗時代價越高。而且它所需要的額外輔助空間較多，達到O(N)級別。想想看，排序140W數據，需要額外再開辟140W的空間，實在是無法忍受。

(7)?多數先進排序都因為跳躍式的比較，降低了比較次數，但是也犧牲了排序的穩定性。

?

?

總的來說，并不存在“最佳”的排序算法。必須針對待排序列自身的特點來選擇“良好”的算法。下面有一些指導性的意見：

(1) 數據規模很小，而且待排序列基本有序的情況下，選擇直接插入排序絕對是上策。不要小看它O(N^2)級別。

(2) 數據規模不是很大，完全可以使用內存空間。而且待排序列雜亂無序(越亂越開心)，快排永遠是不錯的選擇，當然付出log(N)的額外空間是值得的。

(3) 海量級別的數據，必須按塊存放在外存(磁盤)中。此時的歸并排序是一個比較優秀的算法。

?

附：以上兩個圖的數據測試在Pentium 4 CPU 3.06GHZ下，CPU占用率0%的情況下運行的結果。 另外，下面是我測試九種排序算法的C源代碼，可供大家下載使用。

?

?

?

?

?

★ 一個關于O(N*logN)耗時下限的理論

?

這里有一個疑問：是不是O(N*logN)是排序算法時間代價最好的極限呢？

?

當然不是，但是 如果排序算法是基于"關鍵字比較"操作的，那么在最壞情況下確實能夠到達的最好效果就是O(N*logN)了。 在最好情況下就沒必要說了，如果待排序列基本有序，那么直接插入排序的比較次數都非常的少。

?

下面我們來證明一下(注意：這些排序算法的基本操作就是比較，其時間主要消耗在比較次數上)。現在有三個關鍵字K1、K2、K3。那么下圖給出了這三個關鍵字記錄在任何可能的排序狀態下的判定樹，樹中的內部結點都進行了一次必要的比較。

三個關鍵字的待排序列只有上面葉子結點所描述的6中排序狀態。而判定樹上的每一次比較都是必須的。因此、這個判定樹足以描述通過“比較”進行的排序過程。并且，每一個待排序列經過排序達到有序序列所需要進行的"比較"次數，恰為從樹根到葉子結點的路徑長度。因此3個關鍵字的比較最少需要2次，最多需要3次。

?

擴展一下，有N個關鍵字序列。那么就有N!種排序狀態，自然判定樹就有N!個葉子節點。我們知道，二叉樹的樹高為h的情況下，葉子結點最多有2^(h-1)個。而現在又N!個葉子結點，那么樹高至少為log(N!)+1。也就是說，描述N個記錄排序的判定樹必存在一條長度為[log(N!)+1]的路徑。根據斯特林公式(n!的高精度近似求解公式)： log(N!)=N*log(N)。因此，最少的比較次數也就是N*log(N)了。

?

基于比較操作的排序算法的時間復雜度下限確實是O(N*logN)。那么如果不比較呢，耗時代價會不會進一步減少。當然，關于這方面的排序算法，請見《 桶排序 》、《 基數排序 》。

?

?

?

?

【排序結構5】 基于比較的內部排序總結