北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）内排序

插入排序类 template <class Record, class Compare> class InsertSorter: public Sorter<Record, compare>si 北京大学信息学院 版权所有,转载或翻印必究 Page 21

北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 插入排序类 template <class Record,class Compare> class InsertSorter:public Sorter<Record,Compare>{};

直接插入排序 template <class Record, class Compare> class straightinsertsorter public Insertsorter<Record, compare> //直接插入排序类 public void Sort(Record Arrayllint ni ; 北京大学信息学院 版权所有,转载或翻印必究 Page 22

北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 直接插入排序 template <class Record,class Compare> class StraightInsertSorter:public InsertSorter<Record,Compare> { //直接插入排序类 public: void Sort(Record Array[],int n); };

template <class Record, class Compare> bid StraightInsertSorter<Record, Compare>: ort(Record array l int n) ∥/Aay[]为待排序数组,n为数组长度 for(inti=1;i<ni++)//依次插入第i个记录 {//依次与前面的记录进行比较,发现逆置就交换 for(int j=ijj>ojj-t if(Compare:lt(Array ll Array [j-1D) swap(Array, j j-1); else break;∥/此时i前面记录已排序 } 北京大学信息学院 版权所有,转载或翻印必究 Page 23

北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 template <class Record,class Compare> void StraightInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 for (int i=1; i<n; i++) // 依次插入第i个记录 { //依次与前面的记录进行比较，发现逆置就交换 for (int j=i;j>0;j--){ if (Compare::lt(Array[j], Array[j-1])) swap(Array, j, j-1); else break; //此时i前面记录已排序 } } }

算法分析 ■稳定 n空间代价:0(1) 时间代价: 最佳情况:n-1次比较,0次比较,o(n) 最差情况:比较和交换次数为 ∑i=n(n-1)/2=(m2) n平均情况:(n2) 北京大学信息学院 版权所有,转载或翻印必究 Page 24

北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 算法分析 ◼ 稳定 ◼ 空间代价：Θ(1) ◼ 时间代价： ◼ 最佳情况：n-1次比较，0次比较，Θ(n) ◼ 最差情况：比较和交换次数为 ◼ 平均情况：Θ(n2) 1 2 1 ( 1)/ 2 ( ) n i i n n n − =  = − = 

优化的插入排序算法 template <class Record, class Compare> class ImprovedInsertsorterapublic nsertSorter<Record, compare> //优化的插入排序类 public. void Sort(Record arrayllint ni 北京大学信息学院 版权所有,转载或翻印必究 Page 25

北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 优化的插入排序算法 template <class Record,class Compare> class ImprovedInsertSorter:public InsertSorter<Record,Compare> { //优化的插入排序类 public: void Sort(Record Array[],int n); };