李一達(dá)，黃維通

（1.清華大學(xué) 物理系，北京 100084；2.清華大學(xué) 計(jì)算機(jī)系，北京 100084）

0 引 言

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

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

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

1 幾種排序算法效率分析

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

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

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

2 快速二分排序

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

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

劃分操作保證左邊元素小于等于flag，右邊元素大于flag，因而每段子序列（最左邊子序列除外，因?yàn)樗脑卮笥诘扔谧钚≈担┑脑囟夹∮诘扔谒淖畲笾登掖笥谧钚≈?，這保證了最大值和最小值之差為1時(shí)可以結(jié)束排序（該區(qū)間只有一個(gè)可取值）。對(duì)于最左邊子序列，只要調(diào)用排序函數(shù)時(shí)，最小值位置填入a[0]-1即可消除其特殊性（如果不能保證不越界，可換用預(yù)先剔除所有等于a[0]元素的方法，只需一趟類似快速排序的劃分操作，將等于a[0]的元素放到左邊，不等于a[0]的元素放到右邊即可，不會(huì)影響排序效率）。

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

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

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

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

2.2 對(duì)快速二分排序的時(shí)間復(fù)雜度分析

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

1）(max-min)

(max-min)

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

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

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

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

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

可以看出，(max-min)

2） (max-min)≈n。

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

3） (max-min)>n。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 可能的改進(jìn)方向

(max-min)

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

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

4 結(jié) 語(yǔ)

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

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

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

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