template <class record, class compare> VOId improvedInsertSorter<Record, Compare>:: Sort(Record array, int n) ∥/Aay[]为待排序数组,n为数组长度 Record TempRecord//临时变量 /依次插入第个记录 for (int i=1; i<n; i++) TempRecord=Arrayal /从始往前寻找记录的正确位置 intj=i-1i 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 template <class Record,class Compare> void ImprovedInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量 // 依次插入第i个记录 for (int i=1; i<n; i++) { TempRecord=Array[i]; //从i开始往前寻找记录i的正确位置 int j = i-1;
//将那些大于等于记录的记录后移 whie((>=0)&& Compare: :t(TempRecord, Array[D)) ArrayLj+1]= ArrayAl ∥/此时j后面就是记录的正确位置,回填 Array[+1]= TempRecordi 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 //将那些大于等于记录i的记录后移 while ((j>=0) && (Compare::lt(TempRecord, Array[j]))) { Array[j+1] = Array[j]; j = j - 1; } //此时j后面就是记录i的正确位置，回填 Array[j+1] = TempRecord; } }
二分法插入排序 算法思想: 在插入第个记录时,前面的记录 已经是有序的了,可以用二分法 査找第个记录的正确位置。 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 二分法插入排序 ◼ 算法思想： ◼ 在插入第i个记录时，前面的记录 已经是有序的了，可以用二分法 查找第i个记录的正确位置
template <class Record, class Compare> class binaryInsertSorter: public nsertSorter<Record, compare> //二分法插入排序类 public. void Sort(Record arrayllint ni 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 template <class Record,class Compare> class BinaryInsertSorter:public InsertSorter<Record,Compare> { //二分法插入排序类 public: void Sort(Record Array[],int n); };
template <class record, class compare> void BinaryInsertsorter<Record, compare>i: Sort(Record array int n) ∥/Aray[为待排序数组,n为数组长度 Record TempRecordi /临时变量 /记录已排好序序列的左、右、中位置 int left, right, middle /依次插入第个记录 for(int i=1; i<n;i++) /保存当前待插入记录 TempRecord E arrayal; 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 template <class Record,class Compare> void BinaryInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; //临时变量 //记录已排好序序列的左、右、中位置 int left,right,middle; //依次插入第i个记录 for (int i=1;i<n;i++) { //保存当前待插入记录 TempRecord = Array[i];