- 相關(guān)推薦
快速排序里的學(xué)問(wèn)：樞紐元選擇與算法效率
每一練習(xí)都是一次積淀，終將成就不一樣的自己。下面是小編整理的快速排序里的學(xué)問(wèn)之樞紐元選擇與算法效率，希望對(duì)大家有用，更多消息請(qǐng)關(guān)注應(yīng)屆畢業(yè)生網(wǎng)。
選擇首尾元素做樞紐元
通常的、沒(méi)有經(jīng)過(guò)充分考慮的選擇是將第一個(gè)或最后一個(gè)元素用作樞紐元。選擇第一個(gè)元素作為樞紐元的程序例子可以參考專題的前一篇《快速排序里的學(xué)問(wèn)：霍爾快排的實(shí)現(xiàn)》，而選擇最后一個(gè)元素用作樞紐元的程序例子則可以參考《快速排序里的學(xué)問(wèn)：快速排序的過(guò)程》這個(gè)算法導(dǎo)論里的例子。
選擇最后一個(gè)元素作為樞紐元的排序過(guò)程是這樣的：
如果輸入是隨機(jī)的，那么這是可以接受的，但是如果輸入是預(yù)排序的或者是反序的，那么這樣的樞紐元就產(chǎn)生一個(gè)劣質(zhì)的分割，因?yàn)樗械脑夭皇潜粍澣隨1就是被劃入S2。更有甚者，這種情況發(fā)生在所有的遞歸調(diào)用中。
實(shí)際上，如果第一個(gè)元素用作樞紐元而且輸入是預(yù)先排序的，那么快速排序所花費(fèi)的時(shí)間將是二次的。然而，預(yù)排序的輸入(或者有一大段預(yù)排序數(shù)據(jù)的輸入)也是相當(dāng)常見的，因此，使用第一個(gè)元素作為樞紐元的算法效率不是很高的。
另一種想法是選取前兩個(gè)互異的鍵中的較大者作為樞紐元，但這和只選取第一個(gè)元素作為樞紐元效率也差不多。
隨機(jī)選取樞紐元
一種安全的方針是隨機(jī)選取樞紐元。
一般來(lái)說(shuō)這種策略非常安全，除非隨機(jī)數(shù)生成器有問(wèn)題，因?yàn)殡S機(jī)的樞紐元不可能總在接連不斷地產(chǎn)生劣質(zhì)的分割。另一方面，隨機(jī)數(shù)的生成一般是昂貴的，根本減少不了算法其余部分的平均運(yùn)行時(shí)間。
三數(shù)中分割法
一組N個(gè)數(shù)的中值是第[N/2]個(gè)最大的數(shù)。樞紐元的最好的選擇是數(shù)組的中值。
可是，這很難算出來(lái)，并且會(huì)明顯減慢快速排序的速度。這樣的中值的估計(jì)可以通過(guò)隨機(jī)選取三個(gè)元素并用它們的中值作為樞紐元而得到。事實(shí)上，隨機(jī)性并沒(méi)有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的不好情形。
這種樞紐元選擇的的快排，效率可是相當(dāng)高的。
快速排序還很有很多各種變種，我們這里只研究幾個(gè)有代表性的算法。
【快速排序里的學(xué)問(wèn)：樞紐元選擇與算法效率】相關(guān)文章：
PHP 快速排序算法解析06-11
C#排序算法之快速排序09-09
PHP快速排序算法詳解08-30
c#快速排序算法10-21
PHP快速排序算法解析10-09
C語(yǔ)言快速排序算法及代碼06-25
C++選擇排序算法實(shí)例09-26