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