針對快速排序改進的一些思考及其實現(xiàn)

李一達，黃維通

（1.清華大學 物理系，北京 100084；2.清華大學 計算機系，北京 100084）

0 引 言

計算機程序設計基礎課程從算法設計的角度出發(fā)，包含冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸并排序等最基本、最常用的排序算法，提供解決排序問題的多元化思路；對快速排序適當拓展，介紹多種選取基準元素的方法，同時說明快速排序的問題——基準元素的選取直接決定排序的效率。

之所以基于快速排序進行改進，是因為相對其他基于比較的排序算法，快速排序效率較高并被廣泛應用，STL（standard template library）的sort函數(shù)就建立在快速排序的基礎上?？焖倥判蜃钪饕膯栴}在于不管用什么方法選取快速排序的基準元素，總會有使其時間復雜度退化到O(n2)的情況出現(xiàn)。為了減少這種不利情況對排序效率的影響，STL的解決方案是當快速排序的遞歸深度超過某個閾值時，改用堆排序，從而保證時間復雜度仍為O(nlb(n))（本文中l(wèi)b均代表以2為底的對數(shù)）。

針對快速排序的上述問題，有許多跳出快速排序基于比較這一限制的改進方法。文獻[1]提出的高效快速排序，以待排序元素的平均值作為劃分的基準元素以實現(xiàn)較為均勻的劃分。文獻[2]的超快速排序實質上是二進制整數(shù)的基數(shù)排序，不再受劃分不均的影響。

1 幾種排序算法效率分析

文獻[1]提出的高效快速排序用待排序元素的平均值代替隨機選取的基準元素，在大部分情況下保證了均勻的劃分，但是此算法在比較、交換操作之外增加了大量加法運算（每次劃分前計算待排序元素的平均值），nlb(n)次的加法運算必定會使整體的效率有所下降，預期結果就是在快速排序選擇基準元素較合適的情況下高效快速排序更慢。此外，依然有導致此算法劃分極不均勻的特例。例如，待排序的序列為{1,10,100,1 000，10 000,100 000}，每次用平均值作為基準元素，會使劃分極其不平均，從而高效快速排序退化到冒泡排序。高效快速排序可以較好地解決快速排序劃分不均勻問題，但是在提高排序效率方面還有較大提升空間。

文獻[2]提出的超快速排序是采用快速排序劃分方法的二進制基數(shù)排序，劃分的均勻與否不再是影響排序效率的因素，而基數(shù)排序的本質也保證了較高的排序效率，但是排序前，浮點數(shù)要轉化為整數(shù)，并且負數(shù)要單獨處理，這使得超快速排序適用范圍較窄。

快速二分排序雖然不源于對以上兩種算法的思考，但是能夠較好地解決以上兩種算法存在的問題，使快速排序效率提升明顯。

2 快速二分排序

快速二分排序算法描述：在排序開始前找出待排序元素的最小值和最大值，每次以兩者的平均值（取整；對浮點數(shù)保留到最末位）作為基準元素進行劃分，并以此平均值作為劃分出的兩個子序列新的最小值或最大值，當某段子序列待排序元素個數(shù)為1或最大值和最小值之差為1（即整數(shù)的精度；對浮點數(shù)來說，最大值和最小值之差為浮點數(shù)的精度時結束排序，下文涉及的最大值最小值之差的“1”均可等價地用浮點數(shù)的精度替換）時結束對該段子序列的排序。C語言代碼如下。

此算法需要預處理，即在排序開始前將待排序元素的最小值放在序列第1個元素位置，待排序元素的最大值放在序列最后1個元素位置。

劃分操作保證左邊元素小于等于flag，右邊元素大于flag，因而每段子序列（最左邊子序列除外，因為它的元素大于等于最小值）的元素都小于等于它的最大值且大于最小值，這保證了最大值和最小值之差為1時可以結束排序（該區(qū)間只有一個可取值）。對于最左邊子序列，只要調用排序函數(shù)時，最小值位置填入a[0]-1即可消除其特殊性（如果不能保證不越界，可換用預先剔除所有等于a[0]元素的方法，只需一趟類似快速排序的劃分操作，將等于a[0]的元素放到左邊，不等于a[0]的元素放到右邊即可，不會影響排序效率）。

2.1 對預處理環(huán)節(jié)的思考

預處理要同時找出待排序元素的最小值和最大值。兩趟簡單選擇排序可以使用2n次比較解決這個問題，而借鑒歸并排序的做法，可以得到更高效的方案。把尋找待排序元素的最小值和最大值問題分解成兩個子問題（分別對一半數(shù)量的待排序元素尋找最小值和最大值），分別解決后再合并。

有如下表達式（T(n)代表尋找n個元素最小值和最大值需要的比較次數(shù)）：T(n)=2T(n/2)+2，解得T(n)=3n/2-2，這意味著只需要3n/2次比較就能得到最小值和最大值。

實現(xiàn)也較為簡單：每次取兩個元素，比較后分別與當前的最小值和最大值進行比較。這樣每兩個元素只需要3次比較，總的比較次數(shù)就是3n/2。這種實現(xiàn)相比兩趟簡單選擇排序，代碼量會增加很多，并且在將最小值和最大值交換到首、末位置時有較多的特殊情況。為了使代碼簡潔明了，快速二分排序用兩趟簡單選擇排序得到最小值和最大值。

2.2 對快速二分排序的時間復雜度分析

快速二分排序實際上是借用快速排序的劃分方法把最大值和最小值之間的每個整數(shù)都隔離出來，核心仍是二進制基數(shù)排序，其最大遞歸深度是lb(max-min)，因而時間復雜度不會超過O(nlb(max-min))。分3種情況討論（n為待排序元素個數(shù)）。

1）(max-min)

(max-min)

除去最大值和最小值之差這一個特征量，影響排序效率的主要數(shù)據(jù)特征就是較多重復元素的存在。對于重復元素的處理方案（判斷最大值和最小值之差與1的關系）本身就是快速二分排序算法的一部分，(max-min)=1即代表重復元素被排好序。原始快速排序對于重復元素沒有預案，較多的重復元素會導致劃分不均勻。

針對快速排序處理較多重復元素時的較差表現(xiàn)，有3路劃分的改進方法，可避免因重復元素較多而劃分不均勻的情況出現(xiàn)，消除重復元素對快速排序的不利影響。

為了說明快速二分排序的高效性，對快速二分排序與C++庫函數(shù)qsort（使用3路劃分方法的快速排序）進行對比。

圖1所示為快速二分排序（V1版本）與qsort在待排序元素個數(shù)相同、最大值和最小值之差不同情況下的用時比較（快速二分排序計算尋找最小值、最大值和排序的總用時）。

圖1 不同取值范圍（最大值和最小值之差的范圍是9～499 999）下快速二分排序（V1版本）與qsort對比（500 000待排序元素）

可以看出，(max-min)

2） (max-min)≈n。

(max-min)≈n時，如果待排序元素取值的分布較為均勻，主要影響因素就不再是重復元素，而是快速排序無法完全避免的情況——基準元素選取偏差過大，導致劃分嚴重不均勻。對于選取序列首個元素作為基準元素的快速排序，順序序列就能導致快速排序時間復雜度退化到O(n2)。qsort用3點取中的方法確定基準元素，在很大程度上能夠降低這種不利情況發(fā)生的概率，可以確定這樣的例子必定存在，但是快速二分排序不會受到劃分不均勻的影響，(max-min)≈n的前提就已經(jīng)將其最大遞歸深度限制在lb(max-min)（約等于 lb(n)），因而對于滿足 (max-min)≈n的任何待排序序列都會保持O(nlb(max-min)) （約等于O(nlb(n))）的時間復雜度。

3） (max-min)>n。

此時不利于快速二分排序的主要因素是待排序元素取值范圍過大導致遞歸深度過大（待排序元素取值范圍過大不會給快速排序帶來不利影響）。假設(max-min)=nn，那么快速二分排序的時間復雜度O(n2lb(n))甚至超過冒泡排序的O(n2)，但實際中這樣的情況并不多見。由于n較小時插入排序等低級算法與快速排序等高級算法在用時上差距較小，以下討論n≥10 000的情況。

目前32位編譯環(huán)境下int類型的取值范圍約為-2×109～2×109，即使long long int類型取值范圍的最大值和最小值之差也在1019量級，而1019=(104)4.75，即快速二分排序最壞情況（比較次數(shù)達到最大，即nlb((max-min)/n)）的時間開銷僅是正常情況下的4～5倍（數(shù)據(jù)量大時這個比值更小），并且最壞情況可被預判（最大值和最小值之差相比待排序元素個數(shù)過大時可考慮換用其他排序算法），在這一點上好于某些情況下退化到冒泡排序而無法預判的快速排序。

此時快速二分排序的總比較次數(shù)在nlb(n)～nlb(max-min)范圍內。

以一個極端的例子說明快速二分排序可能的最壞情況。假設待排序的序列為{min,min+1,...,min+n-2,max} 且 (max-min)>>n，可以估計總的比較次數(shù)約為nlb((max-min)/n)+nlb(n)，nlb((max-min)/n)表示為了將最大值和最小值之差縮小到n需要lb((max-min)/n)層遞歸，每層遞歸需要n次比較（遍歷一次除最大值外的待排序元素），nlb(n)表示將前n-1個元素分開需要的比較次數(shù)。

最好情況的一種可能是待排序元素的取值在最大值和最小值確定的區(qū)間內均勻分布，即待排序的序列為{min,min+(max-min)/(n-1),min+2×(max-min)/(n-1)......min+(n-2)×(max-min)/(n-1),max}，此時比較次數(shù)是nlb(n)（每次劃分都會使待排序元素數(shù)量規(guī)模減半，因而遞歸深度是lb(n)），而如果有一個元素偏離均勻分布的位置（如和一個相鄰元素大小只差1），為了確定這個元素的位置，排序時需要的遞歸深度就比均勻分布的情況更大，從而使比較次數(shù)增多，隨著偏離均勻分布位置的元素個數(shù)增多，快速二分排序時間復雜度逐漸接近最壞情況。

如果假設輸入的數(shù)據(jù)較為均勻，那么快速二分排序的時間開銷將更接近于nlb(n)次比較，只在少數(shù)情況下退化到nlb(max-min)。雖然一個數(shù)據(jù)就可以使時間復雜度增大，但是鑒于實際應用中收集數(shù)據(jù)時已經(jīng)剔除明顯偏離正常范圍的“壞點”，而且退化的時間復雜度也是O(nlb(n))，因此排序效率不會受到太大影響。

2.3 對快速二分排序與qsort在不同數(shù)據(jù)量下的對比

圖2所示為數(shù)據(jù)取值范圍0～109的情況下，快速二分排序（V1版本）與C++庫函數(shù)qsort在不同數(shù)據(jù)量時的用時比較。

可以看到，快速二分排序（V1版本）相比于qsort有50%左右的速度提升（圖中擬合直線的斜率代表排序一個元素的平均用時，定義此用時的倒數(shù)為排序的速度）。

圖2 不同數(shù)據(jù)量下快速二分排序（V1版本）與qsort對比

2.4 對快速二分排序的優(yōu)化

作為采用3路劃分改進方法的快速排序，C++庫函數(shù)qsort的表現(xiàn)已經(jīng)很出色，而STL中的sort函數(shù)進行了更細致的優(yōu)化，經(jīng)驗表明相同條件下sort用時是qsort的一半，大致的測試結果顯示快速二分排序（V1版本）慢于sort。

《STL源碼剖析》[3]中提到了sort對快速排序進行的幾點主要優(yōu)化措施：①如果分段后的小區(qū)間長度小于某個閾值（書中指明為16），改用插入排序；②如果遞歸深度超過某個閾值（書中指明為2lb(n)），改用堆排序；③書中并不推薦的一點：每次劃分后，sort只對右半段進行遞歸排序，對左半段采用循環(huán)的方式繼續(xù)排序——雖然書中認為這樣降低了可讀性，并且效率不是很高[3]，但實際應用中，遞歸的效率低于循環(huán)，這樣的改進可以減少函數(shù)調用的次數(shù)，應當能適當提升效率。

基于3.2中3）的分析，快速二分排序目前不需要②的優(yōu)化策略，但是①和③所述優(yōu)化方法仍然值得借鑒，為了讓快速二分排序和sort有一定的可比性，我們也對快速二分排序進行①和③的優(yōu)化，代碼如下（劃分操作不變）：

優(yōu)化后的快速二分排序性能提升明顯，達到了能夠同sort進行比較的水平。

圖3是待排序元素取值范圍0～109、不同待排序元素個數(shù)的情況下，快速二分排序（V2版本）和sort的比較結果。

圖3 不同數(shù)據(jù)量下快速二分排序（V2版本）與sort對比

雖然V2版本對快速二分排序的優(yōu)化必定不如STL開發(fā)者對sort的優(yōu)化精細，并且測試條件是不利于快速二分排序的情況（(max-min)>n），但是快速二分排序仍然在較多情況下保持優(yōu)勢，小幅超越sort。

3 可能的改進方向

(max-min)

雖然快速二分排序的時間復雜度只與待排序元素的最大值和最小值之差有關，但是由于我們只利用待排序元素最初的最小值和最大值信息，多次劃分之后將出現(xiàn)較大的誤差積累（即我們記錄的最小值（最大值）遠小于（大于）該區(qū)間元素實際的最小值（最大值）），實際的比較次數(shù)仍然在一定程度上依賴于待排序元素的數(shù)據(jù)特點，取值分布不均勻的數(shù)據(jù)對快速二分排序有著不利影響。然而，又存在如下矛盾：僅在排序前找到待排序元素的最小值和最大值，能夠完全保證遞歸深度最大是lb(max-min)，并保持快速排序的高效性，但是受數(shù)據(jù)分布情況影響較大；如果類似高效快速排序[1]，每次劃分前都重新尋找當前待排序元素的最小值和最大值，雖然做到每次劃分都完全適應當前序列的特點，但是會增加時間開銷。

目前看來，快速二分排序只是一個初級的處理方案，雖然優(yōu)化后的快速二分排序具有等同于甚至超過STL中sort算法的效率，但是仍有較大的改進空間。如何讓二分法更“智能”，減少對重復元素的遍歷次數(shù)，將是改進的方向。

4 結 語

本文對快速排序做出一些并不基于比較的調整，旨在提高快速排序的效率，從根本上解決快速排序時間復雜度退化的問題。實際測試的結果也令人滿意。在目前數(shù)據(jù)存儲范圍有限（指的是通常的32位、64位編譯環(huán)境下）的情況下，快速二分排序具有接近甚至超過STL中sort函數(shù)的性能，并且仍有進一步改進的空間，但就其目前的良好表現(xiàn)來看，快速二分排序已經(jīng)具備了成為標準模板庫排序函數(shù)的素質。

[1] 湯亞玲, 秦鋒. 高效快速排序算法研究[J]. 計算機工程, 2011(6): 77-78.

[2] 周建欽. 超快速排序算法[J]. 計算機工程與應用, 2006(29): 41-42.

[3] 侯捷. STL源碼剖析[M]. 武漢: 華中科技大學出版社, 2011: 389-400.