快速排序算法優(yōu)化策略

李馳

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

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

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

文章編號(hào)：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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int originLow = low，originHigh = high;

int i = low， j = high，current;

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

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

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

//找到第一個(gè)大于middle1的位置i

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

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

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

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

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

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

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

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

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

while（ low < high ）{

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

//如果左邊長(zhǎng)度小于右邊

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

2 總結(jié)

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

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

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

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

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

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

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