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