74基于分治法的排序 分治策略的基本思想 将原始数组分为若干个子部分然 ■分治策略的实例 后分别进行排序 BST査找、插入、删除算法 快速排序、归并排序 两种算法 二分检索 快速排序 主要思想 划分 归并排序 求解子问题(子问题不重叠) 综合解 举位▲张倍墙写 北大单张铭写 叔新有,命邮 Divide-and-Conquer(P)t //问题足够小了就面接求解 if i Pl s cthen <SP; return; y 20世纪十大算法( Computing in //问题过大就分解成子问题 7. 1962London A] Elliot Brothers divide pinto阿,P Ld的 Tony Hoare提出的快速排 角1对子问题分别求解(此处利用递归调 序 for i=1 to k i= Divide-and-Conquer( Pi /综合子问题的解成为问题的解 return Merge(y,y,…y 北真大张写 真大影张帖写 叔新有,量究 253445图 T122964 74.1快速排序 32 ■算法思想 选择轴值( pivot) 将序列划分为两个子序列L和R, 囡 45团6 使得L中所有记录都小于或等于轴 值,R中记录都大于轴值 对子序列L和R递归进行快速排序 最终撸序结果: 122529 34456478 北真大学张铭编写10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 7.4 基于分治法的排序 „ 将原始数组分为若干个子部分然 后分别进行排序 „ 两种算法 „ 快速排序 „ 归并排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 分治策略的基本思想 „ 分治策略的实例 „ BST查找、插入、删除算法 „ 快速排序、归并排序 „ 二分检索 „ 主要思想 „ 划分 „ 求解子问题(子问题不重叠) „ 综合解 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 Divide-and-Conquer(P) { //问题足够小了就直接求解 if |P| ≤ c then {S(P); return; } //问题过大就分解成子问题 divide P into P1, P2, …, Pk //对子问题分别求解（此处利用递归调 用） for i = 1 to k yi = Divide-and-Conquer(Pi) //综合子问题的解成为问题的解 return Merge(y1, y2, …, yk) } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 „ 20世纪十大算法 ( Computing in „ 7. 1962London的Elliot Brothers Ltd的Tony Hoare提出的快速排 序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 7.4.1 快速排序 „ 算法思想： „ 选择轴值（pivot） „ 将序列划分为两个子序列L和R， 使得L中所有记录都小于或等于轴 值，R中记录都大于轴值 „ 对子序列L和R递归进行快速排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 最终排序结果： 12 25 29 32 34 45 64 78 25 34 45 32 78 12 29 64 25 12 29 29 34 45 78 64 12 25 29 34 78 64 32 45 25 64 78