李馳

摘要：為了解決經(jīng)典快速排序算法在面對待排序數(shù)據(jù)事先有序，大量重復(fù)數(shù)據(jù)，遞歸層數(shù)過深以及排序穩(wěn)定性等諸多問題時暴露出來的缺陷，從樞軸的合理選擇、三路劃分、與其他排序法結(jié)合和尾遞歸優(yōu)化等多個方面分析和總結(jié)了優(yōu)化經(jīng)典快速排序算法的各種策略，在實際使用快速排序算法時具有一定的參考價值。

關(guān)鍵詞： 快速排序;算法優(yōu)化;樞軸;三路劃分;排序穩(wěn)定性;尾遞歸優(yōu)化

中圖分類號： TP311? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）01-0226-03

Abstract：In order to solve the problems exposed by the classical quick sort algorithm， such as ordered data in advance， a large number of repeated data， too many recursive layers，and sorting stability， etc， this paper analyzes and summarizes various strategies of optimizing classical quick sort algorithm from the aspects of reasonable selection of pivot， three-way division， combination with other sorting algorithm and tail recursive optimization， it has certain reference value in the actual use of quick sort algorithm.

Key words： quick sort; algorithm optimization;pivot; three-way division; sorting stability; tail recursive optimization

排序一直以來都是計算機(jī)科學(xué)中的一個重要研究問題，尤其是在程序設(shè)計的算法領(lǐng)域。許多專家學(xué)者都在努力找到綜合效率最高的排序算法。衡量排序算法效率的指標(biāo)包括時間復(fù)雜度、空間復(fù)雜度和是否穩(wěn)定等。這些指標(biāo)中最重要的當(dāng)然是時間復(fù)雜度。雖然歸并排序和堆排序的最好和平均時間復(fù)雜度也能夠達(dá)到O（nlogn），但其常數(shù)因子較大，所以快速排序?qū)嶋H上是目前發(fā)現(xiàn)的最快的排序算法。但是這并不意味著快速排序就沒有缺點。事實上，在待排序數(shù)據(jù)事先有序，或者有大量重復(fù)數(shù)據(jù)，或者排序要求穩(wěn)定性時經(jīng)典快速排序算法表現(xiàn)就比較糟糕。所以對于經(jīng)典的快速排序進(jìn)行優(yōu)化就顯得很有必要，本文就從各個不同的角度分析和總結(jié)了對經(jīng)典快速排序的優(yōu)化策略。

1 具體優(yōu)化策略

1.1優(yōu)化不必要的交換

經(jīng)典的快速排序算法需要將作為樞軸的元素在每次掃描停頓時輪流與后面的和前面的元素不斷地進(jìn)行交換。但其實每次交換之后樞軸的記錄位置都是臨時的，而它的最終位置是最后一次交換后的中間位置。所以，我們可以在算法中直接省略掉樞軸記錄多次交換的折騰操作，取而代之是等到它的最終位置確定之后，再將它一次性的移動到中間的正確位置上[1]。雖然每次交換操作也只需要3條語句，但是當(dāng)數(shù)據(jù)量大時，用賦值語句替換交換語句在效率上也是有一些提升的。具體從算法代碼來看，就是有3個變化：

1）在每趟劃分的前面追加一句“L.r[0]=L.r[low];//將樞軸記錄放在哨兵位置”。

2）將經(jīng)典快速排序算法中“swap（L.r[low]， L.r[high]）;”語句替換為賦值語句“L.r[low]=L.r[high]”。另一處也做相應(yīng)對等的替換。

3）在每趟劃分的后面追加一句“L.r[low]=L.r[0];//將哨兵位置的樞軸元素一次性移動到中間的正確位置上?！?/p>

1.2 針對數(shù)據(jù)事先有序的優(yōu)化

如果待排序數(shù)據(jù)是隨機(jī)的，通常經(jīng)典的快速排序算法有很好的時間復(fù)雜度。因為理想情況下，每次劃分的兩個子序列很均勻，即長度差不多，因而遞歸樹的深度約為logn，而每次遞歸的時間花費(fèi)依次為 T（n）、T（n/2）、T（n/4）…T（1） ，最終推算出的時間復(fù)雜度為O（nlogn）。但是當(dāng)待排序數(shù)據(jù)基本有序，甚至極端情況下完全有序（包括順序和倒序）時，由于經(jīng)典快速排序算法使用的樞軸元素通?？偸堑谝粋€元素，導(dǎo)致每次劃分出來的兩個序列及其不平衡。一個為空，另外一個為只比上一次少一個元素的子序列，形成的遞歸樹為一顆斜樹，最終使得快速排序算法退化為冒泡排序，時間復(fù)雜度成為O（n2）。

為了避免這種情況的發(fā)生，需要打破經(jīng)典快速排序算法每次固定選擇第一個元素為樞軸的做法，另外選擇樞軸。比較常見的有以下一些改進(jìn)的做法。

一種做法是每次劃分選擇下標(biāo)為low～high之間的隨機(jī)整數(shù)的數(shù)組元素作為樞軸，這樣可以大概率地避免由于待排序數(shù)據(jù)的有序性每次選到最大值或者最小值作為樞軸。但是這種做法還是和待排序數(shù)據(jù)的分布以及運(yùn)氣有關(guān)，另外調(diào)用隨機(jī)函數(shù)也有一定的系統(tǒng)開銷，而且也很難得到真正的隨機(jī)數(shù)。

另外一種更常見的做法叫“三數(shù)取中”法[2]。即取下標(biāo)為low、（low+high）/2和high三個數(shù)組元素的中間值作為樞軸。這種方法雖然不能百分之百保證每次劃分的兩個子序列絕對均衡，但是由于取到的是中值不是最值，所以可以大概率的保證不會出現(xiàn)極度不平衡的遞歸斜樹。同時三數(shù)取中不需要遍歷整個數(shù)組，只需幾次簡單比較，所以計算開銷不大。

有文獻(xiàn)還提到了一種“均值”法來取樞軸[3]。即將整個數(shù)組的平均值作為樞軸。雖然這種方法比“三數(shù)取中”法有更大的概率得到一顆非常平衡的遞歸樹，但是由于每次劃分都要遍歷整個數(shù)組，會占用較多時間開銷。此外，當(dāng)待排序的數(shù)據(jù)大小極度懸殊時，例如，待排序的序列為{1，10，100，1000，10000，100000}，仍然會使得每次劃分非常不平衡。

1.3 針對數(shù)據(jù)大量重復(fù)的優(yōu)化

排序算法的理論模型往往是一些互不相等的數(shù)據(jù)，但實際生活中的數(shù)據(jù)往往有大量的重復(fù)。例如，某個學(xué)校三千人的數(shù)學(xué)成績大概率的集中在60到100分，這必然有大量的重復(fù)數(shù)據(jù)。經(jīng)典快速排序算法對含有大量重復(fù)數(shù)據(jù)的待排序列的排序效率并不高。

一種常見的應(yīng)對重復(fù)數(shù)據(jù)的改進(jìn)排序算法是“三路劃分快速排序”[4]。它的思想是將待排序序列分為三部分，最前面是所有小于樞軸元素值的元素; 中間是等于樞軸元素值的元素，最后面是所有大于樞軸元素值的元素。這樣由于中間的部分不再是一個元素，而是好幾個相同元素構(gòu)成的一個區(qū)段，從而使得左右兩個子序列的長度縮短了，當(dāng)再次遞歸調(diào)用劃分時效率會得以提高。劃分的示意圖如圖1所示。

但以上的“三路劃分快速排序”有個限制，就是要求樞軸元素剛好是重復(fù)元素。文獻(xiàn)[4]中還提到一種“加強(qiáng)型三路劃分快速排序”，讓中間的那路數(shù)據(jù)不是值等于某個具體值的數(shù)據(jù)，而是在某個范圍的數(shù)據(jù)，這樣即使待排序的數(shù)據(jù)沒有重復(fù)值，被劃分出的中間那路也可以有不止一個元素。因此在本算法中需要有兩個樞軸元素，在這里分別記為 middle1、 middle2?！凹訌?qiáng)型三路劃分快速排序”的劃分示意圖如圖2所示。

實現(xiàn)的核心代碼如下：

void ThrQSort（Sqlist &L，int low，int high）{

int originLow = low，originHigh = high;

int i = low， j = high，current;

//將兩樞軸的值分別初始化為第一和最后一個元素

int middle1 = L.r[low]，middle2 = L.r[high];

if（middle>middle2） swap（middle1，middle2） ;

//找到第一個大于middle1的位置i

while（L.r[i]<= middle1） i++;

//找到第一個小于等于middle2的位置j

while（L.r[j]> middle2） j--;

current = i;

//循環(huán)分3種情況處理中路的數(shù)據(jù)

while（ current <= j）

{

if（L.r[current]<= middle1） swap（L.r[current++]，L.r[i++]） ;

else if（L.r[current]>middle2） swap（L.r[current]，L.r[j--]） ;

else current ++;

}

//分左中右三路遞歸調(diào)用

ThrQSort（ L，originLow， i -1） ;

ThrQSort（ L，i，current -1） ;

ThrQSort（ L，current，originHigh） ;

}

1.4 與其他排序法結(jié)合的優(yōu)化

眾所周知，經(jīng)典快速排序的時間復(fù)雜度是O （nlogn），通常認(rèn)為是低于時間復(fù)雜度為O（n2）的插入排序的，但是這個結(jié)論是建立在數(shù)據(jù)n的規(guī)模很大的前提條件下的。所以，當(dāng)數(shù)據(jù)規(guī)模n很小時（通常認(rèn)為n小于16時），插入排序的時間效率反而優(yōu)于快速排序。因此，當(dāng)遞歸劃分的子序列長度低于16時，我們可以選擇不再遞歸調(diào)用快速排序，轉(zhuǎn)而使用插入排序，這樣可以使得算法效率有所提高。實現(xiàn)這個算法只需要在代碼中加入一句判斷語句：“if（high-low<16）InsertSort（L，low，high）;”。

還可以考慮一種結(jié)合歸并排序的快速排序算法[5]。前面已經(jīng)說過，如果每次劃分導(dǎo)致左右兩個子序列的長度極為不平衡，就會增加遞歸樹的深度，從而影響算法時間效率。所以，一種思路就是對每次劃分出來的兩個子序列的長度進(jìn)行比較， 如果其中一個與另一個的長度比超過某一界限時， 則認(rèn)為這是一個“畸形劃分”， 對較短的子序列繼續(xù)使用快速排序， 而把較長的子序列平分為兩個子序列分別排序， 然后再進(jìn)行一次歸并。

1.5 算法穩(wěn)定性優(yōu)化

經(jīng)典快速排序雖然速度很快，但是排序算法是不穩(wěn)定。所謂排序算法的穩(wěn)定性是指在待排序的記錄序列中，如果存在多個具有相同的關(guān)鍵字的記錄，經(jīng)過排序后，這些記錄的相對次序保持不變，即在原序列中， ri = rj，且 ri 在 rj 之前，而在排序后的序列中， ri 仍在 rj 之前，則稱這種排序算法是穩(wěn)定的，否則稱為不穩(wěn)定的。排序的穩(wěn)定性有時是有實際意義的，例如只對提交作品成績排名前100的人頒獎，如果第100名的成績剛好有幾個并列的，由于獎金有限只對并列成績的第1個人頒獎，這時并列成績的記錄順序就很重要，不希望在排序后改變。文獻(xiàn)[6]給出了一種將經(jīng)典排序算法改進(jìn)為穩(wěn)定排序的方法。具體思路是首先增加與待排序數(shù)據(jù)數(shù)量相同的輔助存儲空間，然后進(jìn)行如下兩個步驟：1）在一趟快速排序中，左邊的low指針與右邊的high指針交替往中間掃描，在左邊的low指針掃描時，將所有小于 middle 值（樞軸）的元素按原順序存放在原來存儲區(qū)最前部 D1 區(qū)，所有不小于 middle 值的元素按原順序連續(xù)存放在輔助存儲區(qū)最前部 T1 區(qū); 在右邊的high指針掃描時，將所有大于等于 middle 值的元素按原順序存放在原來存儲區(qū)最后部 D4 區(qū)，所有小于middle 值的元素按原順序連續(xù)存放在輔助存儲區(qū)最后部 T3 區(qū);2）把T1 區(qū)數(shù)據(jù)復(fù)制到D4區(qū)的前部即D3區(qū)，把T3 區(qū)數(shù)據(jù)復(fù)制到D1區(qū)的后部即D2區(qū)，一趟處理完成。這兩個步驟的示意圖如圖3，圖4所示。

1.6 其他方面的優(yōu)化

1.6.1優(yōu)化遞歸操作

遞歸對性能是有影響的，經(jīng)典的快速排序算法在每次劃分之后有兩次遞歸操作。當(dāng)遞歸層次很深時，例如遞歸樹不平衡，遞歸深度趨于n而不是平衡時的logn，就會占用大量的?？臻g，從而降低性能。采用尾遞歸優(yōu)化[7]，對每次劃分后較短的子序列仍然直接遞歸，而較長的子序列使用尾遞歸方式可以使得這個問題有所改善。實現(xiàn)代碼如下：

void QSort（Sqlist &L，int low，int high）{

while（ low < high ）{

int pivotloc = Partition（L，low，high）;

//如果左邊長度小于右邊

if（pivotloc -low < high- pivotloc ）? ?{

QSort（L， low， pivotloc -1）; //左邊

low = pivotloc + 1 ; //尾遞歸

}

else{

QSort（L， pivotloc +1，high）; //右邊

high = pivotloc -1; //尾遞歸

}}}

1.6.2加入逆序判斷

經(jīng)典的快速排序算法在一趟快速排序中，左邊的low指針與右邊的high指針交替往中間掃描，在這個過程中除了將當(dāng)前元素與樞軸比較大小外沒有再做其他額外的工作，實在有些浪費(fèi)。有一種改進(jìn)思路就是在這個掃描過程中對相鄰元素進(jìn)行逆序檢測[8]，如果檢測到有逆序可以進(jìn)行冒泡交換，甚至如果發(fā)現(xiàn)某一側(cè)的子序列沒有一個逆序時，證明這一側(cè)的子序列已經(jīng)有序，且又位于樞軸的同一側(cè)，則可以直接終止這一側(cè)的遞歸，以節(jié)省系統(tǒng)開銷。

2 總結(jié)

經(jīng)典的快速排序算法是目前已知排序算法中時間復(fù)雜度最好的算法，但是它在面臨待排序數(shù)據(jù)事先有序，大量重復(fù)數(shù)據(jù)以及對排序穩(wěn)定性有要求時仍然存在很多問題需要優(yōu)化。本文從樞軸的合理化選擇、三路劃分、與其他排序法結(jié)合、尾遞歸優(yōu)化等多方面對經(jīng)典排序算法的優(yōu)化策略進(jìn)行了分析和總結(jié)，在實際使用快速排序算法時有一定的參考價值。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.

[2] 李紅麗，袁海根.快速排序的分析與改進(jìn)[J].輕工科技，2012，28（1）：65-66.

[3] 連順金.快速排序的一種改進(jìn)算法[J].三明學(xué)院學(xué)報，2009，26（4）：420-422.

[4] 王善坤，陶禎蓉.一種三路劃分快速排序的改進(jìn)算法[J].計算機(jī)應(yīng)用研究，2012，29（7）：2513-2516.

[5] 劉新，劉任任.用歸并法改進(jìn)快速排序[J].計算技術(shù)與自動化，2005，24（1）：31-33.

[6] 邵順增.穩(wěn)定快速排序算法研究[J].計算機(jī)應(yīng)用與軟件，2014，31（7）：263-266.

[7] 程杰.大話數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2011.

[8] 張曉煜.基于前置、后置策略的快速排序算法研究[J].渭南師范學(xué)院學(xué)報，2018，33（16）：29-37.

【通聯(lián)編輯：唐一東】