int index1=left//左边子序列的起始位置 Array[i++]= TempArraytindex2++]; int index2= middle+1;//右子序列起始位置 int i=left; //从左开始归并 //处理剩余记录 while((index1 < middle)&& while (index1 < middle) (index2 < right))t /取较小者插入合并数组中 Array[i++]= TempArraylindex1++]; while(index2 < right) Array[i++] Temp Array index2++]; Array [i++] Temp Array[index1++]; 举位▲张倍墙写 北大单张铭写 叔新有,命邮 R Sedgewick优化归并思想 2534453278122964) 优化的归并排序 25344532)078122964) efine ThResHold 16 template <class Record, class Compare> (2534)(4532)(812)02964) ay Merge Sorter: public //优化的两路归并排序类 (25)34)(45)(32)(78(12)(29)(64) 填 (25323445)(78642912) ord Array[, Record TempArray [l, int 12252932344564 北真大脆张写 真大影张帖写 叔新有,量究 优化的归并排序(cont) de( eft+right/2//从中间划分 /优化的两路归并排序,Aray[]为特排序数组 /left,rght分别为数组两端 } oid ImprovedTwoway Sorter<Record Compare:: Sort(Record Array[l, Record //直接对子数组进行优化的插入排序 TempArray[, int left, int right)t if (right < left) nsert sorter Sort( &Array [left], right- left+1 //如果序列长度大于鯛值(16最住),跳出递归 if (right-left+1> THRESHOLD) 北真大学张铭编写 聊张帖写 权新有,究 1616 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 91 int index1=left; //左边子序列的起始位置 int index2=middle+1;//右子序列起始位置 int i=left; //从左开始归并 while ((index1 <= middle)&& (index2 <= right)) { //取较小者插入合并数组中 if (Compare::le(TempArray[index1], TempArray[index2])) Array[i++] = TempArray[index1++]; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 92 else Array[i++] = TempArray[index2++]; } //处理剩余记录 while (index1 <= middle) Array[i++] = TempArray[index1++]; while (index2 <= right) Array[i++] = TempArray[index2++]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 93 (25 34 45 32 78 12 29 64) (25 34 45 32)(78 12 29 64) (25 34)(45 32)(78 12)(29 64) (25)(34)(45)(32)(78)(12)(29)(64) (25 34)(45 32)(12 78)(64 29) (25 32 34 45)(78 64 29 12 ) (12 25 29 32 34 45 64 78) 先划分再归并 R.Sedgewick优化归并思想 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 94 优化的归并排序 #define THRESHOLD 16 template <class Record,class Compare> class ImprovedTwoWayMergeSorter:public Sorter<Record,Compare> { //优化的两路归并排序类 private: void Merge(Record Array[], Record TempArray[],int left,int right,int middle);//归并过程 public: void Sort(Record Array[], Record TempArray[], int left, int right); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 95 优化的归并排序（cont.） //优化的两路归并排序，Array[]为待排序数组 //left，right分别为数组两端 template <class Record,class Compare> void ImprovedTwoWayMergeSorter<Record, Compare>::Sort(Record Array[],Record TempArray[], int left, int right) { if (right <= left) return; //如果序列长度大于阈值(16最佳)，跳出递归 if (right-left+1 > THRESHOLD) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 96 { int middle=(left+right)/2; //从中间划分 Sort(Array, TempArray ,left,middle); Sort(Array, TempArray ,middle+1,right); Merge(Array, TempArray ,left,right,middle); } else { //直接对子数组进行优化的插入排序 ImprovedInsertSorter<Record,Compare> insert_sorter; insert_sorter.Sort(&Array[left],right￾left+1); } }