template <class Record, class Compare> void ImprovedInsertsorter<Record, Compare> Sort(Record Arrayal, int n) ∥/Aray[]为待排序数组,n为数组长度 二分法插入排序 Record TempRecord临时变量 for(inti=1i<ni++){//依次插入第个记录 算法思想: /从i始往前寻找记录的正确位量 在插入第个记录时,前面的记录 /将那些大于等于记录记录后移 已经是有序的了 Compare: It(TempRecord, Array[]))& 可以用二分法查找第i个记录的正 Array U+1]= Array u] 确位置 时后面就是记录的正确位量,回填 y[+1]=Ter 举▲张铭物写 北大单张铭写 叔新有,命邮 算法分析 722冒泡排序 稳定 间代价:e(1) 算法思想: ■时间代价: 不停地比较相邻的记录,如果不 插入每个记录需要e(og次比较 满足排序要求,就交换相邻记 最多移动i+1次,最少2次(移动临时记 录,直到所有的记录都已经排好 序 因此最佳情况下总时间代价为 e( nlog n),最差和平均情况下仍为e(n2) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 4534781234322964 ⊥=11245347829343264 冒泡排序类 122 453478 template <class Record class Compare> 4 class BubbleSorter: public 2932a445348 Sorter<Record, compare> //冒泡排序类 i=51229323434456478 void Sort(Record Array [ int n); i=6 1229323434456478 71229323434456478 聊张帖写 权新有,究 55 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 template <class Record,class Compare> void ImprovedInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量 for (int i=1; i<n; i++) { // 依次插入第i个记录 TempRecord=Array[i]; //从i开始往前寻找记录i的正确位置 int j = i-1; //将那些大于等于记录i的记录后移 while ((j>=0) && (Compare::lt(TempRecord, Array[j]))) { Array[j+1] = Array[j]; j = j - 1; } //此时j后面就是记录i的正确位置，回填 Array[j+1] = TempRecord; } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 二分法插入排序 „ 算法思想： „ 在插入第i个记录时，前面的记录 已经是有序的了 „ 可以用二分法查找第i个记录的正 确位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 算法分析 „ 稳定 „ 空间代价：Θ(1) „ 时间代价： „ 插入每个记录需要Θ(log i)次比较 „ 最多移动i+1次 ，最少2次（移动临时记 录） „ 因此最佳情况下总时间代价为 Θ(nlog n) ，最差和平均情况下仍为Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 7.2.2 冒泡排序 „ 算法思想： „ 不停地比较相邻的记录，如果不 满足排序要求，就交换相邻记 录，直到所有的记录都已经排好 序。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 冒泡排序类 template <class Record,class Compare> class BubbleSorter:public Sorter<Record,Compare> { //冒泡排序类 public: void Sort(Record Array[],int n); };