排序 - 交換排序 - 快速排序 （一）

　　快速排序(QuickSort)

　　算法思想

　　快速排序是CRAHoare於年提出的一種劃分交換排序它采用了一種分治的策略通常稱其為分治法(Divideand

　　ConquerMethod)

　　() 分治法的基本思想

　　分治法的基本思想是將原問題分解為若干個規模更小但結構與原問題相似的子問題遞歸地解這些子問題然後將這些子問題

　　的解組合為原問題的解

　　()快速排序的基本思想

　　設當前待排序的無序區為R[lowhigh]利用分治法可將快速排序的基本思想描述為

　　①分解

　　在R[lowhigh]中任選一個記錄作為基准(Pivot)以此基准將當前無序區劃分為左右兩個較小的子區間R[lowpivotpos)和

　　R[pivotpos+high]並使左邊子區間中所有記錄的關鍵字均小於等於基准記錄(不妨記為pivot)的關鍵字pivotkey右邊的子

　　區間中所有記錄的關鍵字均大於等於pivotkey而基准記錄pivot則位於正確的位置(pivotpos)上它無須參加後續的排序

　　注意

　　劃分的關鍵是要求出基准記錄所在的位置pivotpos劃分的結果可以簡單地表示為(注意pivot=R[pivotpos])

　　R[lowpivotpos]keys≤R[pivotpos]key≤R[pivotpos+high]keys

　　其中low≤pivotpos≤high

　　②求解

　　通過遞歸調用快速排序對左右子區間R[lowpivotpos]和R[pivotpos+high]快速排序

　　③組合

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

　　作

　　快速排序算法QuickSort

　　void QuickSort(SeqList Rint lowint high)

　　{ //對R[lowhigh]快速排序

　　int pivotpos; //劃分後的基准記錄的位置

　　if(low

　　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]的排序。tW.WinGWIT.CoM

From:http://tw.wingwit.com/Article/program/sjjg/201311/23795.html