快速排序算法的分析與研究

摘 要： 快速排序是排序算法中性能較好的一種，但存在對數據基本有序的情形下的性能瓶頸問題。為了保證快速排序在任何情況下的高效性，在對快速排序算法的時間效率進行充分的分析的基礎上，指出支點元素的選取是影響快速排序算法效率的主要因素。提出了一種隨機選擇支點元素的快速快排方法，很好地避免了最壞情況的發生。通過實驗驗證了改進算法的正確性和高效性。

關鍵詞： 快速排序算法； 支點元素； 時間效率； 隨機化快速排序

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2013）20?0054?03

快速排序（Quicksort）是一種基于比較、劃分的排序方法。它基本思想是：在待排元素集S中選擇一個元素x作為支點（Pivot），通過一趟排序將要排序的數據分割成獨立的兩個子序列SL和SR，其中左部分SL的所有元素都小于或等于支點元素，而右部分SR的所有元素都大于或等于支點元素（升序排序） ，其狀態如圖1所示。然后按此方法對這兩部分數據分別再進行快速排序，以此達到整個待排元素有序，整個排序過程可以遞歸進行，其遞歸的深度可用二叉樹表示，如圖2所示。從算法的思想可以得出，快速排序算法是利用分治技術的典型例子。通常，大家公認快速排序是基于比較的排序方法中平均比較次數最少、速度最快的排序算法，平均時間復雜度為O（nlbn）。但是，若支點元素選擇不當，在劃分的兩個子序列元素個數極度不平衡時，快速排序有效率會急劇下降，最壞情況下快速排序將蛻變為冒泡排序，其時間復雜度為O（n2），算法的遞歸深度就變成一棵深度為n的單支二叉樹。因此，保證快速排序在任何情況下高效性，近年來被國內學者從各種不同的角度進行了改進與優化[1?6]。

本文在對傳統快速排序算法的優點及缺點進行充分分析的基礎上，指出影響快速排序的關鍵因素，提出一種隨機化的高效排序方法。它對待排序的數據初態沒有任何要求，或者說可以讓任何的數據初態在排序時達到均勻分布，從而使任何輸入數據達到O（nlog n）的時間復雜度。

1 傳統的快速排序算法與分析

1.1 傳統的快速排序算法

快速排序算法采用了分治技術，其分治步驟為：首先，問題劃分。將求解問題分成若干大小不等的子問題；其次，遞歸求解。獨立地解決這些子問題；最后，合并解。將子問題的解歸并成原問題的解。由于快速排序可以采用就地重排，合并解不需要花費時間。因此影響算法的最關鍵的問題是支點元素的選擇方法是否適當，是否可以將問題均等的劃分。

傳統的快速排序算法是從待排數據兩端選取一個元素作為支點元素，其遞歸快速排序算法QuickSort如下：

QuickSort（S，L，H）{

//對待排元素S[L..H]進行快速排序

int m； //標識上次劃分支點元的位置

if l

{

m ←PARTITION（S，L，H）

//調用分治法找到m的值

QuickSort（S，L，m-1）

//對左區間遞歸快排

QuickSort（S，m+1，H）

//對右區間遞歸快排

}}

對待排元素集S進行排序，最初的調用是QuickSort（S，1，length[S]）。而快速排序算法的關鍵是PARTITION過程，它對子元素集S [L..H]進行一趟快速排序或一次劃分：

一次劃分PARTITION的算法步驟為：

Step1 首先定義兩個變量i和j，并初始化i=L，j=H ；

Step2 選取第一個待排元素S[L]作為支點元素，并將支點元賦值給pivot，即執行pivot =S[L]；

Step3 從j位置開始由后向前比較（j-- ），找到第一個小于key（支點元素的關鍵字）的元素S[j]，交換S[i]與S[j]；同時，i++。

Step4 從i位置開始由前向后比較 （i++），找到第一個大于key（支點元素的關鍵字）的S[i]，S[i]與S[j]交換；同時，j--。

Step5 重復執行Step3，Step4，直到i=j。并將S[i]←pivot，返回i值。

1.2 傳統快速排序算法的效率分析

算法的時間開銷主要花費在劃分PARTITION操作上，對長度為n的數據元素進行一次劃分，共需n-1次元素的比較。

（1）最好情況時間復雜度

最好情況下，快速排序的每次劃分所選取的支點元素恰好都是當前待排數據的“中值”元素，每次劃分的結果為：支點元素的左、右兩個子表的長度大致相等，即對半劃分。在此情況下，可得知快速排序要做lg n趟劃分，時間復雜度為C（n）=O（nlg n）。

（2）最壞情況時間復雜度

最壞情況下，快速排序的每次劃分選取的支點元素恰好都是當前待排數據中關鍵字最小（或最大）的元素，每次劃分的結果為：支點左邊的子表為空（或右邊的子表為空），而另一個非空的子表中元素個數僅比劃分前的待排數據中元素個數少1個。 在此情況下，快速排序就要做n-1次劃分，而第i次劃分開始時區間長度為n-i+1，所需的比較次數為n-i（1≤i≤n-1），故總的比較次數達到最大值：

如果按上面給出的劃分算法，當待排元素集S已按遞增有序（或遞減有序）排列時，每次取當前待排數據的第1個元素為支點，那么每次劃分所取的支點就是當前待排數據中關鍵字最小（或最大）的記錄，則快速排序所需的比較次數達到最多。即當元素基本有序時，快速排序的效率反而很低，不及冒泡排序及插入排序。

（3）平均時間復雜度

盡管快速排序的最壞時間為O（n2），但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快的，快速排序亦因此而得名。它的平均時間復雜度為O（nlg n）[4]。

在此選擇同一量級的堆排序進行了比較測試。在相同的環境下，基于C++語言平臺，分以不同規模（100，1 000，10 000，100 000）的隨機數作為測試數據集。在程序中根據數據個數的不同產生的隨機整型數組，然后分別讓不同的排序算法來進行從小到大的排序。這里兩種排序算法在相同的輸入規模中原始無序數據都是一樣的，以此來保證實驗的公正性。每個排序算法中加入計數器來記錄排序過程中的比較次數，同時利用計時函數得出排序時間。

表1為輸入數據規模分別為100，1 000，10 000，100 000時兩個算法的排序時間對比。實驗結果表明，一般情況下，快速排序的效率的確比堆排序要高。

表1 堆排序與快速排序時間比較 ms

（4）空間復雜度

快速排序算法是一個遞歸算法，因此，系統會自動開辟一個棧來輔助算法的執行。最壞情況下，遞歸樹的高度為O（n），所需附加棧的空間為線性量級O（n）。一般情況下，如圖2所示其遞歸樹的高度為O（lg n）， 執行算法所需附加棧的空間為對數量級O（lg n）。

2 快速排序算法的改進

影響快速排序算法效率的主要因素是支點元素的選取。若所選擇的支點元素應能夠將數組S分成大小幾乎相等的部分，就能保證快速排序算法的高效性。

假設S由n個不同元素組成，最好的選擇方法是選擇S中元素的中值作為支點元素。比如，初始元素的關鍵字為：333，4，11，23，57，要應選擇23中值作為支點元素。盡管有些理論上好的算法可以找到待排元素的中值，但由于開銷過大使得快速排序無法在實際中得到實用[7]。比如，先對待排序的數據進行統計、求平均來選取出最佳的支點元素，以確保快速排序的每一次劃分位置都正好處于待排序序列的正中間。其算法的本質是選取了最合適的支點，但選取合適的支點本身是一個很浪費時間的操作，因此其方法只能在某些特定情況下提高排序效率，而在另一些情況下反而效率低于基本快速排序。

針對快速排序支點元素的選取，能夠有效改進排序的效率，而又不額外增加開銷的主要有以下兩種方法。

第1種方法是“三者取中”的規則[8?9]。普遍使用的方法：首先，比較待排數據中第一 、中間和最后一個位置上元素的關鍵字，取三者之中值為支點元素。其次，在劃分開始前將該支點元素和該區間的第1個元素進行交換，此后的劃分過程與1.1所給的PARTITION算法完全相同。實踐表明，采用三元素取中值的規則只需要幾條if語句的判斷即可，在時間上、空間上不會增加額外的開銷，但結果可以大大改善快速排序在最壞情況下的性能。第2種方法就是本文所提出的隨機化快速排序。算法思路：每趟劃分選取哪一位置上的元素作為支點不是固定的，而是用隨機數產生器Random（l，h） 隨機選取位于l和h之間的隨機數t（l≤t≤h），用S[t]作為支點元素。這就打破了傳統快速排序對數據元素初始輸入的依賴，相當于S[l..h]中的元素是隨機分布的。

可以看出，隨機化的快速排序與一般的快速排序算法差別很小。選擇l和h之間中任意一個元素作為支點。只需要將選中的支點元素與第一個位置上的元素互換swap（S[t]，S[l]），之后同樣調用 PARTITION（S，l，h）算法進行劃分。隨機化之后，算法的時間空間開銷沒有增加，但性能卻得到了改善，尤其是對待排序元素基本有序的情況下，不可能導致最壞情況的發生。可以嚴格地證明劃分的每一步以非常大的概率導致均勻劃分，與初始輸入分布無關[10]。經實驗對比，在元素有序情況下，兩種排序算法在規模分別為100，200，500時比較次數的統計情況對比，如表2所示。

表2 元素有序兩種排序比較次數統計

同時，算法的隨機化不僅僅適用于快速排序，也適用于其他需要數據隨機分布的算法。

3 結 語

快速排序是一種經典的排序算法，實例驗證了在數據分布均勻的情況下，其排序的效率優于同量級nlbn的堆排序。但在一些特殊情形，如待排序數據有序，其效率低于或者遠遠低于nlbn數量級，甚至蛻變為n2數量級，相對地限制了快速排序的廣泛應用。因此，針對影響快速排序關鍵問題支點元素的選取，提出了一種隨機選取支點元素的方法，改進了快速排序對待排元素初態的敏感性，通過實驗驗證了該算法的正確性和實用性。但是若輸入數據中有很多的相同數據，隨機化的效果也將直接減弱。

參考文獻

[1] 湯亞玲，秦鋒.高效快速排序算法研究[J].計算機工程，2011（6）：77?79.

[2] 劉娜，佟冶.淺析C語言快速排序算法的改進[J].計算機系統應用，2008（1）：113?115.

[3] 周建欽.超快速排序[J].計算機工程與應用，2006，42（9）：41?42.

[4] 連順金.快速排序的一種改進算法[J].三明學院學報，2009（4）：43?45.

[5] 宋鴻修.分割方式的多線程快速排序算法[J].計算機應用，2010（9）：2374?2378.

[6] 庹清.改進的按位拆分快速排序算法[J].計算機應用，2011（1）：55?57.

[7] 王善坤，陶禎蓉.一種三路劃分快速排序的改進算法[J].計算機應用研究，2012（7）：2513?2516.

[8] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2008.

[9] 秦鋒.數據結構[M].合肥：中國科學技術大學出版社，2007.

[10] 霍紅衛，許進.快速排序算法研究[J].微電子學與計算機，2002（6）：6?9.