快速排序裏的學問：樞紐元選擇與算法效率

每一練習都是一次積澱，終將成就不一樣的自己。下面是小編整理的快速排序裏的學問之樞紐元選擇與算法效率，希望對大家有用，更多消息請關注應屆畢業生網。

　　選擇首尾元素做樞紐元

通常的、沒有經過充分考慮的選擇是將第一個或最後一個元素用作樞紐元。選擇第一個元素作為樞紐元的程序例子可以參考專題的前一篇《快速排序裏的學問：霍爾快排的實現》，而選擇最後一個元素用作樞紐元的程序例子則可以參考《快速排序裏的學問：快速排序的過程》這個算法導論裏的例子。

選擇最後一個元素作為樞紐元的排序過程是這樣的：

如果輸入是隨機的，那麼這是可以接受的，但是如果輸入是預排序的或者是反序的，那麼這樣的樞紐元就產生一個劣質的分割，因為所有的元素不是被劃入S1就是被劃入S2。更有甚者，這種情況發生在所有的遞歸調用中。

實際上，如果第一個元素用作樞紐元而且輸入是預先排序的`，那麼快速排序所花費的時間將是二次的。然而，預排序的輸入(或者有一大段預排序數據的輸入)也是相當常見的，因此，使用第一個元素作為樞紐元的算法效率不是很高的。

另一種想法是選取前兩個互異的鍵中的較大者作為樞紐元，但這和只選取第一個元素作為樞紐元效率也差不多。

　　隨機選取樞紐元

一種安全的方針是隨機選取樞紐元。

一般來説這種策略非常安全，除非隨機數生成器有問題，因為隨機的樞紐元不可能總在接連不斷地產生劣質的分割。另一方面，隨機數的生成一般是昂貴的，根本減少不了算法其餘部分的平均運行時間。

　　三數中分割法

一組N個數的中值是第[N/2]個最大的數。樞紐元的最好的選擇是數組的中值。

可是，這很難算出來，並且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機選取三個元素並用它們的中值作為樞紐元而得到。事實上，隨機性並沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數中值分割法消除了預排序輸入的不好情形。

這種樞紐元選擇的的快排，效率可是相當高的。

快速排序還很有很多各種變種，我們這裏只研究幾個有代表性的算法。