4.62快速排序 怎样具 体实现? 基本思想 任取待排序序列中的某个元素作为基准(一般取第 个元素),将待排序元素分为左右两个子表,左子表 中元素的关键字值均小于或等于基准元素的关键字值, 右子表中元素的关键字值均大于或等于基准元素的关键 字值,然后分别对两个子表继续进行划分,直至每一个 子表只有一个元素或为空为止。最后得到的便是有序序 列
4.6.2 快速排序 一. 基本思想 任取待排序序列中的某个元素作为基准（一般取第 一个元素），将待排序元素分为左右两个子表，左子表 中元素的关键字值均小于或等于基准元素的关键字值， 右子表中元素的关键字值均大于或等于基准元素的关键 字值，然后分别对两个子表继续进行划分，直至每一个 子表只有一个元素或为空为止。最后得到的便是有序序 列。 怎样具 体实现？
快速排序一次划分过程 38204638749112 >思考:怎样为38找位置,正确地实现表的 次划分? 概括地说: 次划分就是从表的两端交替方向地 向中间进行扫描,将小的放到左边,大的放 到右边,作为基准的元素放到中间
概括地说： 一次划分就是从表的两端交替方向地 向中间进行扫描, 将小的放到左边, 大的放 到右边, 作为基准的元素放到中间。 • 快速排序一次划分过程 38 20 46 38 74 91 12 ➢思考：怎样为38找位置，正确地实现表的 一次划分？
快速排序一次划分过为了减少数据的移动将作为 基准的元素暂存到r0中, 最后再放入最终位置 1.指向待划分区域最左端,j指向待划石; 2.保存基准元素的值,r0]=r[i≠ 3.从右向左扫描(首先开始此方向的扫描) j从右向左移动,直到r]keyro]key或i 6.若ri]key> r[o]. key,则r]=r[,j-1,改变扫描方向 7.重复3~6,直到j位置重合(即ij),此位置即最终的划分位置; 8.将基准元素放入最终的划分位置,r[=ro]或r]=r[0
• 快速排序一次划分过程 1． i指向待划分区域最左端，j指向待划分区域最右端; 2. 保存基准元素的值，r[0]=r[i] ; 3. 从右向左扫描(首先开始此方向的扫描) j从右向左移动，直到r[j].keyr[0].key或i==j; 6. 若r[i].key>r[0].key，则 r[j]=r[i], j=j-1，改变扫描方向; 7. 重复3~6，直到i,j位置重合（即i==j），此位置即最终的划分位置； 8. 将基准元素放入最终的划分位置，r[i]=r[0]或r[j]=r[0] 为了减少数据的移动,将作为 基准的元素暂存到r[0]中， 最后再放入最终位置
次划分过程演示 low high 234567 38204638749112 i指向待划分区域最左端(low) 兼涤操兼米 j指向待划分区域最右端(high)
2． r[0]=r[i] 一次划分过程演示 i 38 20 46 38 74 91 12 j 0 1 2 3 4 5 6 7 1． i指向待划分区域最左端（low）； j指向待划分区域最右端（high）； 38 low high
次划分过程演示 2 3838204638749112 3.j从右向左移动直到 兼涤操兼米 r[jkey<r0Jkey或i=
一次划分过程演示 i 38 20 46 38 74 91 12 j 0 1 2 3 4 5 6 7 3. j从右向左移动直到 r[j].key<r[0].key或i==j; 38
次划分过程演示 3838204638749112 4.若 rIil. key<r|0key, 兼涤操兼米 则r[i=a[jl,i=i计1,改变扫描方向;
一次划分过程演示 i 38 20 46 38 74 91 12 j 0 1 2 3 4 5 6 7 4. 若 r[j].key<r[0].key ， 则r[i]=a[j], i=i+1，改变扫描方向; 38 12
次划分过程演示 2 3812204638749112 5.i从左向右移动直到 兼涤操兼米 rli. key>r0key或i=j;
一次划分过程演示 i 12 20 46 38 74 91 12 j 0 1 2 3 4 5 6 7 5. i从左向右移动直到 r[i].key>r[0].key或i==j; 38
次划分过程演示 3812204638749112 6.若r[ikey>r|01key, 兼涤操兼米 则rjl=ai,j=j-1,改变扫描方向;
一次划分过程演示 i 12 20 46 38 74 91 12 j 0 1 2 3 4 5 6 7 6. 若 r[i].key>r[0].key， 则 r[j]=a[i]，j=j-1，改变扫描方向; 38 46
次划分过程演示 low mid high 234567 38 12204638749146 3.j从将基准元素放入最终确 rj定的划分位置(j重合处) mid+high
一次划分过程演示 i 12 20 46 38 74 91 46 0 1 2 3 4 5 6 7 3838 令：mid=j，形成两个子表：low~mid-1和mid+1~high 一次划分过程结束 j low mid high 3. j从右向左移动直到 r[j].key<r[0].key或i==j; 将基准元素放入最终确 i,j位置重合,扫描结束 定的划分位置(i,j重合处)
算法实现 实现一次划分的算法: int Partition (listrll, int i, intj) {r0=r[il;/暂存基准元素到r0中* while(i=r[0]. key) if(i<j) tri=rail; i++; while(i<j&&ri]. key<=r[0. key i++; if (i<j 兼涤操兼米 trlilrlj--; ri-r0;/将基准元素放到其最终位置* return i;返回基准元素所在的位置*
• 实现一次划分的算法： int Partition(list r[],int i,intj) { r[0]=r[i]; /* 暂存基准元素到r[0]中*/ while(i=r[0].key) j--; if(i<j) { r[i]=r[j]; i++; } while(i<j&&r[i].key<=r[0].key) i++; if (i<j) { r[j]=r[i]; j--; } } r[i]=r[0]; /* 将基准元素放到其最终位置*/ return i; /*返回基准元素所在的位置*/ } 二. 算法实现
