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]key<r0]key或可; 4.若rU]key< r[O]. key,则r]=ri,j=+1,改变扫描方向; 5.从左向右扫描 i从左向右移动,直到]key>ro]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].key<r[0].key或i==j; 4. 若 r[j].key<r[0].key ，则r[i]=r[j], i=i+1，改变扫描方向； 5. 从左向右扫描： i从左向右移动，直到r[i].key>r[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