★ 基于“比較”操作的內(nèi)部排序性能大PK

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

1、 O(N^2)級別的普通排序算法，我們用C++的隨機(jī)函數(shù)rand()產(chǎn)生的隨機(jī)數(shù)進(jìn)行排序，并計算耗費(fèi)時間。

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

 

 

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

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

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

 

 

從上圖可以發(fā)現(xiàn)，先進(jìn)排序的耗時代價遠(yuǎn)遠(yuǎn)小于普通排序算法。而先進(jìn)算法之間也有區(qū)別。其中快速排序無疑是最優(yōu)秀的。其次是歸并排序和希爾排序，堆排序稍微差一些，而最差的就是樹形選擇排序了。

先進(jìn)算法分析：

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

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

(3) 希爾排序的性能讓人有點(diǎn)意外，這種增量插入排序的高效性完全說明了：在基本有序序列中，直接插入排序絕對能達(dá)到令人吃驚的效率。但是希爾排序?qū)υ隽康倪x擇標(biāo)準(zhǔn)依然沒有較為滿意的答案，要知道增量的選取直接影響排序的效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

三個關(guān)鍵字的待排序列只有上面葉子結(jié)點(diǎn)所描述的6中排序狀態(tài)。而判定樹上的每一次比較都是必須的。因此、這個判定樹足以描述通過“比較”進(jìn)行的排序過程。并且，每一個待排序列經(jīng)過排序達(dá)到有序序列所需要進(jìn)行的"比較"次數(shù)，恰為從樹根到葉子結(jié)點(diǎn)的路徑長度。因此3個關(guān)鍵字的比較最少需要2次，最多需要3次。

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

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