算法之快速排序

快速排序 是1962年提出的一種劃分交換排序。它采用了一種分治的政策，通常稱為分治法 （Divide-and-Conquer Method）。

分治法的基本思想 ：

将原問題分解為若幹個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然後将這些子問題的解組合為原問題的解。

快速排序的基本思想 ：

設目前待排序的無序區為R[low..high]，利用分治法可将快速排序的基本思想描述為：

(1) 分解 

在R[low..high]中任選一個記錄作為基準（Pivot），以此基準将目前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1]和R[pivotpos+1..high]，并使 左邊子區間中所有記錄的關鍵字均<=基準記錄的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均>=pivot.key，而基準記錄pivot則位于正确的位置（pivotpos）上，它無須參加後續的排序。

(2) 求解 

通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]分别進行快速排序。

(3) 組合 

因為當“求解”步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，“組合”步驟無須做什麼，可看做是空操作。