快速排序(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]的