本文介紹第二種交換排序方法：快速排序。
快速排序是 C.R.A.Hoare 于 1962 年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
分治法的基本思想是：將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
設(shè)當(dāng)前待排序的無(wú)序區(qū)為 R[low..high]，利用分治法可將快速排序的基本思想描述為：
1.分解：
在 R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間 R[low..pivotpos-1)和 R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為 pivot)的關(guān)鍵字 pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于 pivot.key，而基準(zhǔn)記錄 pivot 則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序。
注意： 劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置 pivotpos。劃分的結(jié)果可以簡(jiǎn)單地表示為(注意 pivot=R[pivotpos])： R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys 其中 low≤pivotpos≤high。
2.求解：
通過遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間 R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
3.組合：
因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。
void QuickSort(SeqList R，int low，int high)
{ //對(duì)R[low..high]快速排序
int pivotpos； //劃分后的基準(zhǔn)記錄的位置
if(low<high){//僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序
pivotpos=Partition(R，low，high)； //對(duì)R[low..high]做劃分
QuickSort(R，low，pivotpos-1)； //對(duì)左區(qū)間遞歸排序
QuickSort(R，pivotpos+1，high)； //對(duì)右區(qū)間遞歸排序
}
} //QuickSort 注意： 為排序整個(gè)文件，只須調(diào)用 QuickSort(R，1，n)即可完成對(duì) R[l..n]的排序。
1.具體做法
第一步：(初始化)設(shè)置兩個(gè)指針 i 和 j，它們的初值分別為區(qū)間的下界和上界，即 i=low，i=high；選取無(wú)序區(qū)的第一個(gè)記錄 R[i](即 R[low])作為基準(zhǔn)記錄，并將它保存在變量 pivot 中；
第二步：令 j 自 high 起向左掃描，直到找到第 1 個(gè)關(guān)鍵字小于 pivot.key 的記錄 R[j]，將 R[j])移至 i 所指的位置上，這相當(dāng)于 R[j] 和基準(zhǔn) R[i](即 pivot)進(jìn)行了交換，使關(guān)鍵字小于基準(zhǔn)關(guān)鍵字 pivot.key 的記錄移到了基準(zhǔn)的左邊，交換后 R[j]中相當(dāng)于是 pivot；然后，令 i 指針自 i+1 位置開始向右掃描，直至找到第 1 個(gè)關(guān)鍵字大于 pivot.key 的記錄 R[i]，將 R[i]移到 i 所指的位置上，這相當(dāng)于交換了 R[i] 和基準(zhǔn) R[j]，使關(guān)鍵字大于基準(zhǔn)關(guān)鍵字的記錄移到了基準(zhǔn)的右邊，交換后 R[i] 中又相當(dāng)于存放了 pivot；接著令指針 j 自位置 j-1 開始向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至 i=j 時(shí)，i便是基準(zhǔn) pivot 最終的位置，將 pivot 放在此位置上就完成了一次劃分。
2.一次劃分過程
一次劃分過程中，具體變化情況【參見動(dòng)畫演示】
3.劃分算法
int Partition(SeqList R，int i，int j)
{//調(diào)用Partition(R，low，high)時(shí)，對(duì)R[low..high]做劃分，
//并返回基準(zhǔn)記錄的位置
ReceType pivot=R[i]； //用區(qū)間的第1個(gè)記錄作為基準(zhǔn) '
while(i<j){ //從區(qū)間兩端交替向中間掃描，直至i=j為止
while(i<j&&R[j].key>=pivot.key) //pivot相當(dāng)于在位置i上
j--； //從右向左掃描，查找第1個(gè)關(guān)鍵字小于pivot.key的記錄R[j]
if(i<j) //表示找到的R[j]的關(guān)鍵字<pivot.key
R[i++]=R[j]； //相當(dāng)于交換R[i]和R[j]，交換后i指針加1
while(i<j&&R[i].key<=pivot.key) //pivot相當(dāng)于在位置j上
i++； //從左向右掃描，查找第1個(gè)關(guān)鍵字大于pivot.key的記錄R[i]
if(i<j) //表示找到了R[i]，使R[i].key>pivot.key
R[j--]=R[i]; //相當(dāng)于交換R[i]和R[j]，交換后j指針減1
} //endwhile
R[i]=pivot； //基準(zhǔn)記錄已被最后定位
return i；
} //partition 快速排序執(zhí)行的全過程可用遞歸樹來(lái)描述。
分析：
注意： 任何遞歸算法均可用遞歸樹來(lái)描述其執(zhí)行過程。
[49 38 65 97 76 13 27 49] //初始關(guān)鍵字 [27 38 13] 49 [76 97 65 49] //第 1 次劃分完成之后，對(duì)應(yīng)遞歸樹第 2 層 [13] 27 [38] 49 [49 65] 76 [97] //對(duì)上一層各無(wú)序區(qū)劃分完成后，對(duì)應(yīng)遞歸樹第 3 層 13 27 38 49 49 [65] 76 97 //對(duì)上一層各無(wú)序區(qū)劃分完成后，對(duì)應(yīng)遞歸樹第 4 層 13 27 38 49 49 65 76 97 //最后的排序結(jié)果
快速排序的時(shí)間主要耗費(fèi)在劃分操作上，對(duì)長(zhǎng)度為 k 的區(qū)間進(jìn)行劃分，共需 k-1 次關(guān)鍵字的比較。
最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個(gè)非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無(wú)序區(qū)中記錄個(gè)數(shù)減少一個(gè)。 因此，快速排序必須做 n-1 次劃分，第i次劃分開始時(shí)區(qū)間長(zhǎng)度為 n-i+1，所需的比較次數(shù)為 n-i(1≤i≤n-1)，故總的比較次數(shù)達(dá)到最大值：Cmax = n(n-1)/2=O(n2)
如果按上面給出的劃分算法，每次取當(dāng)前無(wú)序區(qū)的第 1 個(gè)記錄為基準(zhǔn)，那么當(dāng)文件的記錄已按遞增序(或遞減序)排列時(shí)，每次劃分所取的基準(zhǔn)就是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最小(或最大)的記錄，則快速排序所需的比較次數(shù)反而最多。
在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)的"中值"記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無(wú)序子區(qū)間的長(zhǎng)度大致相等?？偟年P(guān)鍵字比較次數(shù)：O(nlgn)
注意： 用遞歸樹來(lái)分析最好情況下的比較次數(shù)更簡(jiǎn)單。因?yàn)槊看蝿澐趾笞蟆⒂易訁^(qū)間長(zhǎng)度大致相等，故遞歸樹的高度為 O(lgn)，而遞歸樹每一層上各結(jié)點(diǎn)所對(duì)應(yīng)的劃分過程中所需要的關(guān)鍵字比較次數(shù)總和不超過n，故整個(gè)排序過程所需要的關(guān)鍵字比較總次數(shù) C(n)=O(nlgn)。
因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以快速排序的最壞時(shí)間復(fù)雜度應(yīng)為 O(n2)，最好時(shí)間復(fù)雜度為 O(nlgn)。
在當(dāng)前無(wú)序區(qū)中選取劃分的基準(zhǔn)關(guān)鍵字是決定算法性能的關(guān)鍵。
"三者取中"的規(guī)則
"三者取中"規(guī)則，即在當(dāng)前區(qū)間里，將該區(qū)間首、尾和中間位置上的關(guān)鍵字比較，取三者之中值所對(duì)應(yīng)的記錄作為基準(zhǔn)，在劃分開始前將該基準(zhǔn)記錄和該區(qū)伺的第1個(gè)記錄進(jìn)行交換，此后的劃分過程與上面所給的 Partition 算法完全相同。
取位于 low 和 high 之間的隨機(jī)數(shù)k(low≤k≤high)，用 R[k] 作為基準(zhǔn)
選取基準(zhǔn)最好的方法是用一個(gè)隨機(jī)函數(shù)產(chǎn)生一個(gè)取位于 low 和 high 之間的隨機(jī)數(shù) k(low≤k≤high)，用 R[k] 作為基準(zhǔn)，這相當(dāng)于強(qiáng)迫R[low..high]中的記錄是隨機(jī)分布的。用此方法所得到的快速排序一般稱為隨機(jī)的快速排序。
注意： 隨機(jī)化的快速排序與一般的快速排序算法差別很小。但隨機(jī)化后，算法的性能大大地提高了，尤其是對(duì)初始有序的文件，一般不可能導(dǎo)致最壞情況的發(fā)生。算法的隨機(jī)化不僅僅適用于快速排序，也適用于其它需要數(shù)據(jù)隨機(jī)分布的算法。
盡管快速排序的最壞時(shí)間為 O(n2)，但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，快速排序亦因此而得名。它的平均時(shí)間復(fù)雜度為 O(nlgn)。
快速排序在系統(tǒng)內(nèi)部需要一個(gè)棧來(lái)實(shí)現(xiàn)遞歸。若每次劃分較為均勻，則其遞歸樹的高度為 O(lgn)，故遞歸后需?？臻g為 O(lgn)。最壞情況下，遞歸樹的高度為 O(n)，所需的棧空間為 O(n)。
快速排序是非穩(wěn)定的，例如[2，2，1]。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多