45‖34781234322964 i=134.45‖781234322964 i=2344578‖1234322964 i=312344578‖3432296 i=41234344578‖32296 51232343445782964 i=612293234344578‖64 i=71229323434456478‖
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 45‖ 34 78 12 3 4 32 29 64 i=1 34 45‖ 78 12 3 4 32 29 64 i=2 34 45 78‖ 12 3 4 32 29 64 i=3 12 34 45 78‖ 3 4 32 29 64 i=4 12 34 3 4 45 78‖ 32 29 64 i=5 12 32 34 3 4 45 78‖ 29 64 i=6 12 29 32 34 3 4 45 78‖ 64 i=7 12 29 32 34 3 4 45 64 78‖
template <class Record, class Compare> /Aray[]为待排序数组,n为数组长度e>: cbid StraightInsertSorter<Record, Comp fort(Record array tl int n) for(inti=1i<ni++)//依次插入第个记录 ∥/依次与前面的记录进行比较,发现逆置就交换 for(int j=i;j>O;j-t if (Compare: :lt(Arrayal, Array[j-1D) swap(array,jj-1); else break: /此时前面记录已排序 } 北系大学信息学院张铭编写 版权所有,转载或翻印必究 age 22
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 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前面记录已排序 } } }
算法分析 稳定 空间代价:⊙(1) 时间代价: n最佳情况:n-1次比较,0次交换,(n) ■最差情况:比较和交换次数为 ∑i=n(n-1)/2=(n) 平均情况:⊙(n2) 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 23
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 算法分析 稳定 空间代价：Θ(1) 时间代价： 最佳情况：n-1次比较，0次交换，Θ(n) 最差情况：比较和交换次数为 平均情况：Θ(n2) 1 2 1 ( 1) / 2 ( ) n i i nn n − = ∑ = − =Θ
优化的插入排序算法 template <class Record, class Compare> class ImprovedInsertSorter: public InsertSorter<Record, compare> //优化的插入排序类 public: void Sort(Record Arrayal,int n; 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 24
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 优化的插入排序算法 template <class Record,class Compare> class ImprovedInsertSorter:public InsertSorter<Record,Compare> { //优化的插入排序类 public: void Sort(Record Array[],int n); };
template <class Record, class Compare> void ImprovedInsertsorter< Record, compare>:: Sort(Record array int n) //Aray[]为待排序数组,n为数组长度 Record TempRecord;//临时变量 for(inti=1;i<ni++){//依次插入第个记录 TempRecord=Array[] //从千开始往前寻找记录的正确位置 intj=i-1; /将那些大于等于记录的记录后移 while((>=0)&& Compare: :It(Temp Record, array[iD))< Array[+1]= array[; j=j-1 /此时j后面就是记录的正确位置,回填 Array[+1]= TempRecordi } 北京大学息学院张铭编写 版权所有,转载或翻印必究 age 25
北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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; } }