§10.3.2快速排序（续） §10.3.2快速排序（续） 快速排序的思想：设待排序的无序区为R[low.high void QuickSort(SegList R,int low,int high){ ①裂新弯直前的无序区蓬一记录作为准以生准 对Rlow.high时快速排序 int pivotpos; Rflow..pivotpos-1].keysR[pivotpos].key f(low<high){/当区间长度大于1时须排序 ≤[pivotpos+1.high].k@ys(⑧.1式 pivotpos=Partition(R,low,high);对Rlow.high划分 显然盖准记录已在正确位置上，其余两子区间排序方法与 QuickSort(R,low,pivotpos-1;对左区间递归排序 原问题相同 QuickSort(R,pivotpos+-1,high对右区间递归排序 ①求解：通过递归调用快速排序对左、右子区间排序，当 子区间长度小于等于时无须排。 ②组合：当step②中两个递归调用结束时，其左右子区间 内已有序，敏R[low.high时自然有序，即组合绿作为空 为排序整个文件，只须调用QuickSort(R,1,n)即可完 操作。 成对R[1.n的排序。 §10.3.2快速排序（续） §10.3.2快速排序（续） 如何划分 初始 [4938659776132749 设两个指针i,j,初始时i=low,j=high 取排序区间第1个记录作基准：pivot=R0(即R[low) 令j从后往前扫描，直至找到第1个key小于pivot..key的记 录R门将风]移至所指的位具（相当 于R和R交 向前 [4938659776132749] 换，注意交换前R们pvOt,交换后善准记录相当学在 R[j]中，++) 国令指针从前住后扫描，真到找到第1个关德字大于 pivot.key的记录R叮，将R叮移到j所指位量（相当于交换 第1次交换后+ [2738659776134949 R叮和基准R[j],交换后R可中又相当于存放了pvot, ®热惑亮.处皮早找， 向后 [2738659776134949 22 §10.3.2快速排序（续） §10.3.2快速排序（续） 2nd交换后j [2738499776136549 int Partition(SeqList R,inti,int调用时=low,户high Rectype pivot=-R门：∥区间第1个记录为蓝灌 whie(心s【从区间商端交警肉中间扫捕至判为止 while(i&RIj].kayP=R门.kay)pivot相当于在R可 向前扫描 [2738139776496549] 位置不变交换后+ H业从后往前扫指，找第1个k©y小于善准关铺字的记录R们 计（豪示找到风j】 Ri+=R风[j]:∥相当于交换R可和R,变换后加1，pivot在R风j] 向后扫描 [2738134976976549 while (i<j &R[i].key<=R[].key) 位置不变交换后引 'j +;Ⅲ从前柱后扫描，找第1个k©y大于盖准关抛字的记录R风可 计s)豪示到R风门 j向前，完成 [2738134976976549 R[H门=R0:湘当于交换R门和R0,交换后减1，pwot回到R回 " )所时蜂止 R门=pivot;落准记录已被量后定位 return i;19 §10.3.2 快速排序（续） „ 快速排序的思想：设待排序的无序区为R[low..high] ① 分解：在当前的无序区选一记录作为基准，以此基准将 其划分为： R[low..pivotpos-1].keys≤R[pivotpos].key ≤R[pivotpos+1..high].keys (9.1式) 显然基准记录已在正确位置上，其余两子区间排序方法与 原问题相同 ① 求解：通过递归调用快速排序对左、右子区间排序，当 子区间长度小于等于1时无须排。 ② 组合：当step②中两个递归调用结束时，其左右子区间 内已有序，故R[low..high]自然有序，即组合操作为空 操作。 20 §10.3.2 快速排序（续） 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(R, 1, n)即可完 成对R[1..n]的排序。 21 §10.3.2 快速排序（续） „ 如何划分 ① 设两个指针i，j，初始时i=low, j=high ② 取排序区间第1个记录作基准：pivot=R[i]（即R[low]） ③ 令j从后往前扫描，直至找到第1个key小于pivot.key的记 录R[ j ]，将R[ j ]移至i所指的位置（相当于R[j]和R[i]交 换，注意交换前R[i]=pivot，交换后基准记录相当于在 R[ j ]中，i++） ④ 令 i指针从前往后扫描，直到找到第1个关键字大于 pivot.key的记录R[i]，将R[i]移到j所指位置（相当于交换 R[i]和基准R[ j ]，交换后R[i]中又相当于存放了pivot，j- - ）。 ⑤ 重复③④，如此交换改变扫描方向，从两端向中间靠拢， 直至i=j，i便是基准pivot最终的位置，将pivot放于此。 22 §10.3.2 快速排序（续） j向前 [49 38 65 97 76 13 27 49] i j 第1次交换后i++ [27 38 65 97 76 13 49 49] i j i向后 [27 38 65 97 76 13 49 49] i j 初始 [49 38 65 97 76 13 27 49] i j 23 §10.3.2 快速排序（续） 2nd交换后j-- [27 38 49 97 76 13 65 49] i j j向前扫描 [27 38 13 97 76 49 65 49] i j 位置不变交换后i++ i向后扫描 [27 38 13 49 76 97 65 49] i j 位置不变交换后j-- j向前，完成 [27 38 13 49 76 97 65 49] i j 24 §10.3.2 快速排序（续） int Partition(SeqList R, int i, int j){ //调用时i=low, j=high Rectype pivot=R[i]; //区间第1个记录为基准 while (i<j) { //从区间两端交替向中间扫描至i=j为止 while (i<j && R[ j ].key>= R[i].key) //pivot相当于在R[i] j--; //从后往前扫描，找第1个key小于基准关键字的记录R[ j ] if (i<j) //表示找到R[ j ] R[i++] = R[ j ]; //相当于交换R[i]和R[j]，交换后i加1，pivot在R[ j ] while (i<j && R[i].key<=R[j].key) i++; //从前往后扫描，找第1个key大于基准关键字的记录R[ i] if (i<j) //表示找到R[ i] R[ j--] = R[i]; //相当于交换R[i]和R[j]，交换后j减1，pivot回到R[i] } //i=j时终止 R[i] = pivot; //基准记录已被最后定位 return i; }