快速排序(QuickSort)
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
（2）快速排序的基本思想
設(shè)當(dāng)前待排序的無序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：
①分解：
在R[low..high]中任選一個記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個較小的子區(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)上，它無須參加后續(xù)的排序。
注意：
劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos。劃分的結(jié)果可以簡單地表示為(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中l(wèi)ow≤pivotpos≤high。
②求解：
通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③組合：
因為當(dāng) "求解 "步驟中的兩個遞歸調(diào)用結(jié)束時，其左、右兩個子區(qū)間已有序。對快速排序而言， "組合 "步驟無須做什么，可看作是空操作。
2、快速排序算法QuickSort
void QuickSort(SeqList R，int low，int high)
{ //對R[low..high]快速排序
int pivotpos； //劃分后的基準(zhǔn)記錄的位置
if(low <high){//僅當(dāng)區(qū)間長度大于1時才須排序
pivotpos=Partition(R，low，high)； //對R[low..high]做劃分
QuickSort(R，low，pivotpos-1)； //對左區(qū)間遞歸排序
QuickSort(R，pivotpos+1，high)； //對右區(qū)間遞歸排序
}
} //QuickSort
注意：
為排序整個文件，只須調(diào)用QuickSort(R，1，n)即可完成對R[l..n]的排序。
上一頁 下一頁
3、劃分算法Partition
（1） 簡單的劃分方法
① 具體做法
第一步：(初始化)設(shè)置兩個指針i和j，它們的初值分別為區(qū)間的下界和上界，即i=low，i=high；選取無序區(qū)的第一個記錄R[i](即R[low])作為基準(zhǔn)記錄，并將它保存在變量pivot中；
第二步：令j自high起向左掃描，直到找到第1個關(guān)鍵字小于pivot.key的記錄R[j]，將R[j])移至i所指的位置上，這相當(dāng)于R[j]和基準(zhǔn)R[i](即pivot)進行了交換，使關(guān)鍵字小于基準(zhǔn)關(guān)鍵字pivot.key的記錄移到了基準(zhǔn)的左邊，交換后R[j]中相當(dāng)于是pivot；然后，令i指針自i+1位置開始向右掃描，直至找到第1個關(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時，i便是基準(zhǔn)pivot最終的位置，將pivot放在此位置上就完成了一次劃分。
②一次劃分過程
一次劃分過程中，具體變化情況【參見動畫演示】
③劃分算法：
int Partition(SeqList R，int i，int j)
{//調(diào)用Partition(R，low，high)時，對R[low..high]做劃分，
//并返回基準(zhǔn)記錄的位置
ReceType pivot=R[i]； //用區(qū)間的第1個記錄作為基準(zhǔn) '
while(i <j){ //從區(qū)間兩端交替向中間掃描，直至i=j為止
while(i <j&&R[j].key> =pivot.key) //pivot相當(dāng)于在位置i上
j--； //從右向左掃描，查找第1個關(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個關(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
4、快速排序執(zhí)行過程
快速排序執(zhí)行的全過程可用遞歸樹來描述。
（圖省略）
分析：
（1）遞歸執(zhí)行的路線如圖中帶箭頭的包絡(luò)線所示。
（2） 遞歸樹上每一結(jié)點左旁方括號表示當(dāng)前待排序的區(qū)間，結(jié)點內(nèi)的關(guān)鍵字是劃分的基準(zhǔn)關(guān)鍵字
注意：
葉結(jié)點對應(yīng)的子區(qū)間只有一個關(guān)鍵字，無須劃分，故葉結(jié)點內(nèi)沒有基準(zhǔn)關(guān)鍵字
（3） 劃分后得到的左、右兩個子區(qū)間分別標(biāo)在該結(jié)點的左、右兩個孩子結(jié)點的左邊方括號內(nèi)。
【例】根結(jié)點左旁方括號[49，38，65，97，76，13，27，49]表示初始待排序的關(guān)鍵字，根內(nèi)的49表示所選的劃分基準(zhǔn)記錄的關(guān)鍵字，劃分結(jié)果是[27，28，13]49[76，97，65，49_]，其左右子區(qū)間分別標(biāo)在根結(jié)點的兩個孩子的左邊。
（4） 每個分支結(jié)點右旁圓括號中的內(nèi)容表示對該結(jié)點左旁區(qū)間的排序過程結(jié)束之后返回的結(jié)果。它是其左右孩子對應(yīng)的區(qū)間排序完成之后，將左右孩子對應(yīng)的排序結(jié)果分別放在該分支結(jié)點的關(guān)鍵字前后所得到的關(guān)鍵字序列。
【例】分支結(jié)點76的左右孩子對應(yīng)的區(qū)間排序后的結(jié)果分別是(49_，65)和(97)，將它們分別放在76的前后即得(49，65，76，97)，這是對結(jié)點76左旁區(qū)間[76，97，，65，49]排序的結(jié)果。
（5） 算法的執(zhí)行順序是遞歸樹中的箭頭順序，實際上當(dāng)把劃分操作視為訪問結(jié)點的操作時，快速排序的執(zhí)行過程相當(dāng)于是先序遍歷其遞歸樹。
注意：
任何遞歸算法均可用遞歸樹來描述其執(zhí)行過程。
5、快速排序各次劃分后的狀態(tài)變化
[49 38 65 97 76 13 27 49] //初始關(guān)鍵字
[27 38 13] 49 [76 97 65 49] //第1次劃分完成之后，對應(yīng)遞歸樹第2層
[13] 27 [38] 49 [49 65] 76 [97] //對上一層各無序區(qū)劃分完成后，對應(yīng)遞歸樹第3層
13 27 38 49 49 [65] 76 97 //對上一層各無序區(qū)劃分完成后，對應(yīng)遞歸樹第4層
13 27 38 49 49 65 76 97 //最后的排序結(jié)果
6、算法分析
快速排序的時間主要耗費在劃分操作上，對長度為k的區(qū)間進行劃分，共需k-1次關(guān)鍵字的比較。
（1）最壞時間復(fù)雜度
最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。
因此，快速排序必須做n-1次劃分，第i次劃分開始時區(qū)間長度為n-i+1，所需的比較次數(shù)為n-i(1≤i≤n-1)，故總的比較次數(shù)達(dá)到最大值：
Cmax = n(n-1)/2=O(n2)
如果按上面給出的劃分算法，每次取當(dāng)前無序區(qū)的第1個記錄為基準(zhǔn)，那么當(dāng)文件的記錄已按遞增序(或遞減序)排列時，每次劃分所取的基準(zhǔn)就是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，則快速排序所需的比較次數(shù)反而最多。
（2） 最好時間復(fù)雜度
在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的 "中值 "記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個無序子區(qū)間的長度大致相等。總的關(guān)鍵字比較次數(shù)：
0(nlgn)
注意：
用遞歸樹來分析最好情況下的比較次數(shù)更簡單。因為每次劃分后左、右子區(qū)間長度大致相等，故遞歸樹的高度為O(lgn)，而遞歸樹每一層上各結(jié)點所對應(yīng)的劃分過程中所需要的關(guān)鍵字比較次數(shù)總和不超過n，故整個排序過程所需要的關(guān)鍵字比較總次數(shù)C(n)=O(nlgn)。
因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)，所以快速排序的最壞時間復(fù)雜度應(yīng)為0(n2)，最好時間復(fù)雜度為O(nlgn)。
（3）基準(zhǔn)關(guān)鍵字的選取
在當(dāng)前無序區(qū)中選取劃分的基準(zhǔn)關(guān)鍵字是決定算法性能的關(guān)鍵。
① "三者取中 "的規(guī)則
"三者取中 "規(guī)則，即在當(dāng)前區(qū)間里，將該區(qū)間首、尾和中間位置上的關(guān)鍵字比較，取三者之中值所對應(yīng)的記錄作為基準(zhǔn)，在劃分開始前將該基準(zhǔn)記錄和該區(qū)伺的第1個記錄進行交換，此后的劃分過程與上面所給的Partition算法完全相同。
②取位于low和high之間的隨機數(shù)k(low≤k≤high)，用R[k]作為基準(zhǔn)
選取基準(zhǔn)最好的方法是用一個隨機函數(shù)產(chǎn)生一個取位于low和high之間的隨機數(shù)k(low≤k≤high)，用R[k]作為基準(zhǔn)，這相當(dāng)于強迫R[low..high]中的記錄是隨機分布的。用此方法所得到的快速排序一般稱為隨機的快速排序。具體算法【參見教材】
注意：
隨機化的快速排序與一般的快速排序算法差別很小。但隨機化后，算法的性能大大地提高了，尤其是對初始有序的文件，一般不可能導(dǎo)致最壞情況的發(fā)生。算法的隨機化不僅僅適用于快速排序，也適用于其它需要數(shù)據(jù)隨機分布的算法。
（4）平均時間復(fù)雜度
盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復(fù)雜度為O(nlgn)。
（5）空間復(fù)雜度
快速排序在系統(tǒng)內(nèi)部需要一個棧來實現(xiàn)遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(lgn)，故遞歸后需棧空間為O(lgn)。最壞情況下，遞歸樹的高度為O(n)，所需的棧空間為O(n)。
（6）穩(wěn)定性
快速排序是非穩(wěn)定的，例如[2，2，1]。
轉(zhuǎn)自：
http://www.360doc.com/content/10/1025/15/4161063_63868950.shtml