北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第七章 内排序

二分法插入排序 算法思想: 在插入第个记录时,前面的记录 已经是有序的了 可以用二分法查找第个记录的正 确位置 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 26

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 二分法插入排序 „ 算法思想： „ 在插入第i个记录时，前面的记录 已经是有序的了 „ 可以用二分法查找第i个记录的正 确位置

算法分析 稳定 空间代价:⊙(1) 时间代价: 插入每个记录需要⊙(og)次比较 最多移动i+1次,最少2次(移动临时记 录) 因此最佳情况下总时间代价为 ( nlog n),最差和平均情况下仍为⊙(n2) 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 27

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 算法分析 „ 稳定 „ 空间代价：Θ(1) „ 时间代价： „ 插入每个记录需要Θ(log i)次比较 „ 最多移动i+1次 ，最少2次（移动临时记 录） „ 因此最佳情况下总时间代价为 Θ(nlog n) ，最差和平均情况下仍为Θ(n2)

722冒泡排序 算法思想: 不停地比较相邻的记录,如果不 满足排序要求,就交换相邻记 录,直到所有的记录都已经排好 序。 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 28

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 7.2.2 冒泡排序 „ 算法思想： „ 不停地比较相邻的记录，如果不 满足排序要求，就交换相邻记 录，直到所有的记录都已经排好 序

4534781234322964 1245347829343264 122945 478323464 12293245 464 122932344534786 1229323434456478 i=6 1229323434456478 71229323434456478

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 45 34 78 12 3 4 32 29 64 i=1 12 45 34 78 29 3 4 32 64 i=2 12 29 45 34 78 32 3 4 64 i=3 12 29 32 45 34 78 3 4 64 i=4 12 29 32 34 45 3 4 78 64 i=5 12 29 32 34 3 4 45 64 78 i=6 12 29 32 34 3 4 45 64 78 i=7 12 29 32 34 3 4 45 64 78

冒泡排序类 template <class Record, class Compare> class Bubble Sorter public Sorter< Record, compare> //冒泡排序类 public: void Sort(Record Arrayal,int n; 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 30

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 冒泡排序类 template <class Record,class Compare> class BubbleSorter:public Sorter<Record,Compare> { //冒泡排序类 public: void Sort(Record Array[],int n); };