快速排序(QuickSort)
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
（2）快速排序的基本思想
設(shè)當(dāng)前待排序的無(wú)序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：
①分解：
在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
其中l(wèi)ow≤pivotpos≤high。
②求解：
通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③組合：
因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。
2、快速排序算法QuickSort
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]的