快速排序算法
快速排序（Quick Sort）的基本思想是：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。
假設(shè)現(xiàn)在要對(duì)數(shù)組{50,10,90,30,70,40,80,60,20}進(jìn)行排序。我們通過(guò)代碼的講解來(lái)學(xué)習(xí)快速排序的精妙。
我們來(lái)看代碼。
/* 對(duì)順序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L, 1, L->length);
}
又是一句代碼，和歸并排序一樣，由于需要遞歸調(diào)用，因此我們外封裝了一個(gè)函數(shù)?，F(xiàn)在我們來(lái)看QSort的實(shí)現(xiàn)。
/* 對(duì)順序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L, int low, int high)
{
int pivot;
if (low < high)
{
/* 將L->r[low..high]一分為二， */
/* 算出樞軸值pivot */
pivot = Partition(L, low, high);
/* 對(duì)低子表遞歸排序 */
QSort(L, low, pivot - 1);
/* 對(duì)高子表遞歸排序 */
QSort(L, pivot + 1, high);
}
}
從這里，你應(yīng)該能理解前面代碼“QSort(L,1,L->length);”中1和L->length代碼的意思了，它就是當(dāng)前待排序的序列最小下標(biāo)值low和最大下標(biāo)值high。
這一段代碼的核心是“pivot=Parti-tion(L,low,high);”在執(zhí)行它之前，L.r的數(shù)組值為{50,10,90,30,70,40,80,60,20}。Partition函數(shù)要做的，就是先選取當(dāng)中的一個(gè)關(guān)鍵字，比如選擇第一個(gè)關(guān)鍵字50，然后想盡辦法將它放到一個(gè)位置，使得它左邊的值都比它小，右邊的值比它大，我們將這樣的關(guān)鍵字稱為樞軸（pivot）。
在經(jīng)過(guò)Partition(L,1,9)的執(zhí)行之后，數(shù)組變成{20,10,40,30,50,70,80,60,90}，并返回值5給pivot，數(shù)字5表明50放置在數(shù)組下標(biāo)為5的位置。此時(shí)，計(jì)算機(jī)把原來(lái)的數(shù)組變成了兩個(gè)位于50左和右小數(shù)組{20,10,40,30}和{70,80,60,90}，而后的遞歸調(diào)用“QSort(L,1,5-1);”和“QSort(L,5+1,9);”語(yǔ)句，其實(shí)就是在對(duì){20,10,40,30}和{70,80,60,90}分別進(jìn)行同樣的Partition操作，直到順序全部正確為止。
到了這里，應(yīng)該說(shuō)理解起來(lái)還不算困難。下面我們就來(lái)看看快速排序最關(guān)鍵的Partition函數(shù)實(shí)現(xiàn)。
/* 交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置 */
/* 此時(shí)在它之前（后）的記錄均不大（?。┯谒?*/
int Partition(SqList *L, int low, int high)
{
int pivotkey;
/* 用子表的第一個(gè)記錄作樞軸記錄 */
pivotkey = L->r[low];
/* 從表的兩端交替向中間掃描 */
while (low < high)
{
while (low < high && L->r[high] >= pivotkey)
high--;
/* 將比樞軸記錄小的記錄交換到低端 */
swap(L, low, high);
while (low < high && L->r[low] <= pivotkey)
low++;
/* 將比樞軸記錄大的記錄交換到高端 */
swap(L, low, high);
}
/* 返回樞軸所在位置 */
return low;
}
1．程序開始執(zhí)行，此時(shí)low=1，high=L.length=9。第4行，我們將L.r[low]=L.r[1]=50賦值給樞軸變量piv-otkey，如下圖所示。
2．第5～13行為while循環(huán)，目前l(fā)ow=1<high=9，執(zhí)行內(nèi)部語(yǔ)句。
3．第7行，L.r[high]=L.r[9]=20≯piv-otkey=50，因此不執(zhí)行第8行。
4．第9行，交換L.r[low]與L.r[high]的值，使得L.r[1]=20，L.r[9]=50。為什么要交換，就是因?yàn)橥ㄟ^(guò)第7行的比較知道，L.r[high]是一個(gè)比pivotkey=50（即L.r[low]）還要小的值，因此它應(yīng)該交換到50的左側(cè)，如下圖所示。
5．第10行，當(dāng)L.r[low]=L.r[1]=20，piv-otkey=50，L.r[low]<pivotkey，因此第11行，low++，此時(shí)low=2。繼續(xù)循環(huán)，L.r[2]=10<50，low++，此時(shí)low=3。L.r[3]=90>50，退出循環(huán)。
6．第12行，交換L.r[low]=L.r[3]與L.r[high]=L.r[9]的值，使得L.r[3]=50，L.r[9]=90。此時(shí)相當(dāng)于將一個(gè)比50大的值90交換到了50的右邊。注意此時(shí)low已經(jīng)指向了3，如下圖所示。
7．繼續(xù)第5行，因?yàn)閘ow=3<high=9，執(zhí)行循環(huán)體。
8．第7行，當(dāng)L.r[high]=L.r[9]=90，piv-otkey=50，L.r[high]>pivotkey，因此第8行，high--，此時(shí)high=8。繼續(xù)循環(huán)，L.r[8]=60>50，high--，此時(shí)high=7。L.r[7]=80>50，high--，此時(shí)high=6。L.r[6]=40<50，退出循環(huán)。
9．第9行，交換L.r[low]=L.r[3]=50與L.r[high]=L.r[6]=40的值，使得L.r[3]=40，L.r[6]=50，如下圖所示。
10．第10行，當(dāng)L.r[low]=L.r[3]=40，piv-otkey=50，L.r[low]<pivotkey，因此第11行，low++，此時(shí)low=4。繼續(xù)循環(huán)L.r[4]=30<50，low++，此時(shí)low=5。L.r[5]=70>50，退出循環(huán)。
11．第12行，交換L.r[low]=L.r[5]=70與L.r[high]=L.r[6]=50的值，使得L.r[5]=50，L.r[6]=70，如下圖所示。
12．再次循環(huán)。因low=5<high=6，執(zhí)行循環(huán)體后，low=high=5，退出循環(huán)，如下圖所示。
13．最后第14行，返回low的值5。函數(shù)執(zhí)行完成。接下來(lái)就是遞歸調(diào)用“QSort(L,1,5-1);”和“QSort(L,5+1,9);”語(yǔ)句，對(duì){20,10,40,30}和{70,80,60,90}分別進(jìn)行同樣的Partition操作，直到順序全部正確為止。我們就不再演示了。
通過(guò)這段代碼的模擬，大家應(yīng)該能夠明白，Partition函數(shù)，其實(shí)就是將選取的pivotkey不斷交換，將比它小的換到它的左邊，比它大的換到它的右邊，它也在交換中不斷更改自己的位置，直到完全滿足這個(gè)要求為止。
快速排序復(fù)雜度分析
快速排序的時(shí)間性能取決于快速排序遞歸的深度，可以用遞歸樹來(lái)描述遞歸算法的執(zhí)行情況。如下圖所示，它是{50,10,90,30,70,40,80,60,20}在快速排序過(guò)程中的遞歸過(guò)程。由于我們的第一個(gè)關(guān)鍵字是50，正好是待排序的序列的中間值，因此遞歸樹是平衡的，此時(shí)性能也比較好。
在最優(yōu)情況下，Partition每次都劃分得很均勻，如果排序n個(gè)關(guān)鍵字，其遞歸樹的深度就為（表示不大于x的最大整數(shù)），即僅需遞歸log2n次，需要時(shí)間為T(n)的話，第一次Par-tiation應(yīng)該是需要對(duì)整個(gè)數(shù)組掃描一遍，做n次比較。然后，獲得的樞軸將數(shù)組一分為二，那么各自還需要T(n/2)的時(shí)間（注意是最好情況，所以平分兩半）。于是不斷地劃分下去，我們就有了下面的不等式推斷。
T(n) ≤ 2T(n / 2) + n, T(1) = 0
T(n) ≤ 2(2T(n / 4) + n / 2) + n = 4T(n / 4)+2n
T(n) ≤ 4(2T(n / 8) + n / 4) + 2n = 8T(n / 8)+3n
……
T(n) ≤ nT(1) + (log2n) × n = O(nlogn)
也就是說(shuō)，在最優(yōu)的情況下，快速排序算法的時(shí)間復(fù)雜度為O(nlogn)。
在最壞的情況下，待排序的序列為正序或者逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列，注意另一個(gè)為空。如果遞歸樹畫出來(lái)，它就是一棵斜樹。此時(shí)需要執(zhí)行n-1次遞歸調(diào)用，且第i次劃分需要經(jīng)過(guò)n-i次關(guān)鍵字的比較才能找到第i個(gè)記錄，也就是樞軸的位置，因此比較次數(shù)為sigma(i=1, n-1, n-i)=(n-1)+(n-2)+...+1=n(n-1)/2，最終其時(shí)間復(fù)雜度為O(n2)。
平均的情況，設(shè)樞軸的關(guān)鍵字應(yīng)該在第k的位置（1≤k≤n），那么：
由數(shù)學(xué)歸納法可證明，其數(shù)量級(jí)為O(nlogn)。
就空間復(fù)雜度來(lái)說(shuō)，主要是遞歸造成的?？臻g的使用，最好情況，遞歸樹的深度為log2n，其空間復(fù)雜度也就為O(logn)，最壞情況，需要進(jìn)行n-1遞歸調(diào)用，其空間復(fù)雜度為O(n)，平均情況，空間復(fù)雜度也為O(logn)。
可惜的是，由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此，快速排序是一種不穩(wěn)定的排序方法。
快速排序優(yōu)化
1．優(yōu)化選取樞軸
如果我們選取的pivotkey是處于整個(gè)序列的中間位置，那么我們可以將整個(gè)序列分成小數(shù)集合和大數(shù)集合了。但注意，我剛才說(shuō)的是“如果……是中間”，那么假如我們選取的pivotkey不是中間數(shù)又如何呢？比如我們前面講冒泡和簡(jiǎn)單選擇排序一直用到的數(shù)組{9,1,5,8,3,7,4,6,2}，由代碼第4行“pivotkey=L->r[low];”知道，我們應(yīng)該選取9作為第一個(gè)樞軸pivotkey。此時(shí)，經(jīng)過(guò)一輪“pivot=Partition(L,1,9);”轉(zhuǎn)換后，它只是更換了9與2的位置，并且返回9給pivot，整個(gè)系列并沒(méi)有實(shí)質(zhì)性的變化，如下圖所示。
就是說(shuō)，代碼第4行“pivotkey=L->r[low];”變成了一個(gè)潛在的性能瓶頸。排序速度的快慢取決于L.r[1]的關(guān)鍵字處在整個(gè)序列的位置，L.r[1]太小或者太大，都會(huì)影響性能(比如第一例子中的50就是一個(gè)中間數(shù)，而第二例子的9就是一個(gè)相對(duì)整個(gè)序列過(guò)大的數(shù))。因?yàn)樵诂F(xiàn)實(shí)中，待排序的系列極有可能是基本有序的，此時(shí)，總是固定選取第一個(gè)關(guān)鍵字（其實(shí)無(wú)論是固定選取哪一個(gè)位置的關(guān)鍵字）作為首個(gè)樞軸就變成了極為不合理的作法。
改進(jìn)辦法，有人提出，應(yīng)該隨機(jī)獲得一個(gè)low與high之間的數(shù)rnd，讓它的關(guān)鍵字L.r[rnd]與L.r[low]交換，此時(shí)就不容易出現(xiàn)這樣的情況，這被稱為隨機(jī)選取樞軸法。應(yīng)該說(shuō)，這在某種程度上，解決了對(duì)于基本有序的序列快速排序時(shí)的性能瓶頸。不過(guò)，隨機(jī)就有些撞大運(yùn)的感覺(jué)，萬(wàn)一沒(méi)撞成功，隨機(jī)到了依然是很小或很大的關(guān)鍵字怎么辦呢？
再改進(jìn)，于是就有了三數(shù)取中（median-of-three）法。即取三個(gè)關(guān)鍵字先進(jìn)行排序，將中間數(shù)作為樞軸，一般是取左端、右端和中間三個(gè)數(shù)，也可以隨機(jī)選取。這樣至少這個(gè)中間數(shù)一定不會(huì)是最小或者最大的數(shù)，從概率來(lái)說(shuō)，取三個(gè)數(shù)均為最小或最大數(shù)的可能性是微乎其微的，因此中間數(shù)位于較為中間的值的可能性就大大提高了。由于整個(gè)序列是無(wú)序狀態(tài)，隨機(jī)選取三個(gè)數(shù)和從左中右端取三個(gè)數(shù)其實(shí)是一回事，而且隨機(jī)數(shù)生成器本身還會(huì)帶來(lái)時(shí)間上的開銷，因此隨機(jī)生成不予考慮。
我們來(lái)看看取左端、右端和中間三個(gè)數(shù)的實(shí)現(xiàn)代碼，在Partition函數(shù)代碼的第3行與第4行之間增加這樣一段代碼。
int pivotkey;
/* 計(jì)算數(shù)組中間的元素的下標(biāo) */
int m = low + (high - low) / 2;
if (L->r[low] > L->r[high])
/* 交換左端與右端數(shù)據(jù)，保證左端較小 */
swap(L, low, high);
if (L->r[m] > L->r[high])
/* 交換中間與右端數(shù)據(jù)，保證中間較小 */
swap(L, high, m);
if (L->r[m] > L->r[low])
/* 交換中間與左端數(shù)據(jù)，保證左端較小 */
swap(L, m, low);
/* 此時(shí)L.r[low]已經(jīng)為整個(gè)序列左中右三個(gè)關(guān)鍵字的中間值。 */
/*用子表的第一個(gè)記錄作樞軸記錄 */
pivotkey = L->r[low];
試想一下，我們對(duì)數(shù)組{9,1,5,8,3,7,4,6,2}，取左9、中3、右2來(lái)比較，使得L.r[low]=3，一定要比9和2來(lái)得更為合理。
三數(shù)取中對(duì)小數(shù)組來(lái)說(shuō)有很大的概率選擇到一個(gè)比較好的pivotkey，但是對(duì)于非常大的待排序的序列來(lái)說(shuō)還是不足以保證能夠選擇出一個(gè)好的pivotkey，因此還有個(gè)辦法是所謂九數(shù)取中（me-dian-of-nine），它先從數(shù)組中分三次取樣，每次取三個(gè)數(shù)，三個(gè)樣品各取出中數(shù)，然后從這三個(gè)中數(shù)當(dāng)中再取出一個(gè)中數(shù)作為樞軸。顯然這就更加保證了取到的pivotkey是比較接近中間值的關(guān)鍵字。
2．優(yōu)化不必要的交換
從上面的圖中，我們發(fā)現(xiàn)，50這個(gè)關(guān)鍵字，其位置變化是1→9→3→6→5，可其實(shí)它的最終目標(biāo)就是5，當(dāng)中的交換其實(shí)是不需要的。因此我們對(duì)Partition函數(shù)的代碼再進(jìn)行優(yōu)化。
/* 快速排序優(yōu)化算法 */
int Partition1(SqList *L, int low, int high)
{
int pivotkey;
/* 這里省略三數(shù)取中代碼 */
/* 用子表的第一個(gè)記錄作樞軸記錄 */
pivotkey = L->r[low];
/* 將樞軸關(guān)鍵字備份到L->r[0] */
L->r[0] = pivotkey;
/* 從表的兩端交替向中間掃描 */
while (low < high)
{
while (low < high && L->r[high] >= pivotkey)
high--;
/* 采用替換而不是交換的方式進(jìn)行操作 */
L->r[low] = L->r[high];
while (low < high && L->r[low] <= pivotkey)
low++;
/* 采用替換而不是交換的方式進(jìn)行操作 */
L->r[high] = L->r[low];
}
/* 將樞軸數(shù)值替換回L.r[low] */
L->r[low] = L->r[0];
/* 返回樞軸所在位置 */
return low;
}
我們事實(shí)將piv-otkey備份到L.r[0]中，然后在之前是swap時(shí)，只作替換的工作，最終當(dāng)low與high會(huì)合，即找到了樞軸的位置時(shí)，再將L.r[0]的數(shù)值賦值回L.r[low]。因?yàn)檫@當(dāng)中少了多次交換數(shù)據(jù)的操作，在性能上又得到了部分的提高。如下圖所示。
3．優(yōu)化小數(shù)組時(shí)的排序方案
剛才我談到了對(duì)于非常大的數(shù)組的解決辦法。那么相反的情況，如果數(shù)組非常小，其實(shí)快速排序反而不如直接插入排序來(lái)得更好（直接插入是簡(jiǎn)單排序中性能最好的）。其原因在于快速排序用到了遞歸操作，在大量數(shù)據(jù)排序時(shí)，這點(diǎn)性能影響相對(duì)于它的整體算法優(yōu)勢(shì)而言是可以忽略的，但如果數(shù)組只有幾個(gè)記錄需要排序時(shí)，這就成了一個(gè)大炮打蚊子的大問(wèn)題。因此我們需要改進(jìn)一下QSort函數(shù)。
#define MAX_LENGTH_INSERT_SORT 7 /* 數(shù)組長(zhǎng)度閥值 */
/* 對(duì)順序表L中的子序列L.r[low..high]作快速排序 */
void QSort(SqList &L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
/* 當(dāng)high-low大于常數(shù)時(shí)用快速排序 */
/* 將L.r[low..high]一分為二， */
/* 并算出樞軸值pivot */
pivot = Partition(L, low, high);
/* 對(duì)低子表遞歸排序 */
QSort(L, low, pivot - 1);
/* 對(duì)高子表遞歸排序 */
QSort(L, pivot + 1, high);
}
else
/* 當(dāng)high-low小于等于常數(shù)時(shí)用直接插入排序 */
InsertSort(L);
}
我們?cè)黾恿艘粋€(gè)判斷，當(dāng)high-low不大于某個(gè)常數(shù)時(shí)（有資料認(rèn)為7比較合適，也有認(rèn)為50更合理，實(shí)際應(yīng)用可適當(dāng)調(diào)整），就用直接插入排序，這樣就能保證最大化地利用兩種排序的優(yōu)勢(shì)來(lái)完成排序工作。
4．優(yōu)化遞歸操作
遞歸對(duì)性能是有一定影響的，QSort函數(shù)在其尾部有兩次遞歸操作。如果待排序的序列劃分極端不平衡，遞歸深度將趨近于n，而不是平衡時(shí)的log
2n，這就不僅僅是速度快慢的問(wèn)題了。棧的大小是很有限的，每次遞歸調(diào)用都會(huì)耗費(fèi)一定的?？臻g，函數(shù)的參數(shù)越多，每次遞歸耗費(fèi)的空間也越多。因此如果能減少遞歸，將會(huì)大大提高性能。
于是我們對(duì)QSort實(shí)施尾遞歸優(yōu)化。來(lái)看代碼。
/* 對(duì)順序表L中的子序列L.r[low..high]作快速排序 */
void QSort1(SqList *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
/* L.r[low..high]一分為二, */
/* 算出樞軸值pivot */
pivot = Partition1(L, low, high);
/* 對(duì)低子表遞歸排序 */
QSort1(L, low, pivot - 1);
/* 尾遞歸 */
low = pivot + 1;
}
}
else
InsertSort(L);
}
當(dāng)我們將if改成while后（見(jiàn)加粗代碼部分），因?yàn)榈谝淮芜f歸以后，變量low就沒(méi)有用處了，所以可以將pivot+1賦值給low，再循環(huán)后，來(lái)一次Partition(L,low,high)，其效果等同于“QSort(L,pivot+1,high);”。結(jié)果相同，但因采用迭代而不是遞歸的方法可以縮減堆棧深度，從而提高了整體性能。
