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

?

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

排序方法 ? ? ??

平均時(shí)間 ?

最壞時(shí)間??

輔助存儲(chǔ)空間

? 穩(wě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)	????? ×

簡(jiǎn)單選擇排序????	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) 級(jí)別的普通排序算法，我們用 C++ 的隨機(jī)函數(shù) rand() 產(chǎn)生的隨機(jī)數(shù)進(jìn)行排序，并計(jì)算耗費(fèi)時(shí)間。

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

?

?

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

?

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

?

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

?

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

?

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

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

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

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

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

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

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

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

?

?

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

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

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

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

?

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

?

?

?

?

?

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

?

這里有一個(gè)疑問(wèn)：是不是O(N*logN)是排序算法時(shí)間代價(jià)最好的極限呢？

?

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

?

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

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

?

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

?

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

?

?

?

?

【排序結(jié)構(gòu)5】 基于比較的內(nèi)部排序總結(jié)