优化的归并函数 ate <class Record, class Compare> 开始归并 rter<Record, Compa r(index1=left, index 2=right, k=left; k++ int middle) 〔 TempArray[ [ index1], //归并过程 /两个 Array[k]= TempArray[index1++]; else int i,j, k i for(i= left; i= middle;++)//复制左边的子序列 Arraykk]= TempArray [index2--]: empArray[]= Array[i] /复制右边的子序列,但顺序顺倒过来 Idle; j++) TempArray[right-j+1]= Array[+middle]; 举位▲张倍墙写 北大单张铭写 叔新有,命邮 时间代价 划分时间 两个子序列的排序时间 ■归并时间,n T(n)=2T(n/2)+cn T(1)=1 归并排序总时间代价也为 o(nlog n) 北真大脆张写 版叔斯有就即究 北真大张写 算法分析 算法分析(续) 空间代价:(m) ■稳定 ■总时间代价:⊙(川ogm) 优化 ■不依赖于原始数组的输入情况, 同优化的快速排序一样,对基本 最大、最小以及平均时间代价均 已排序序列直接插入排序 为e(mogm)。 R Sedgewick优化:归并时从两 端开始处理,向中间推进 真大带息学张铭端写 北真大脆张铭编写 1717 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 97 优化的归并函数 template <class Record,class Compare> void ImprovedTwoWayMergeSorter<Record,Compa re>::Merge(Record Array[],Record TempArray[],int left,int right,int middle) { //归并过程 int index1,index2; //两个子序列的起始位置 int i,j,k ; for (i=left; i<=middle; i++)//复制左边的子序列 TempArray[i] = Array[i]; //复制右边的子序列，但顺序颠倒过来 for (j=1; j<=right-middle; j++) TempArray[right-j+1] = Array[j+middle]; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 98 // 开始归并 for (index1=left,index2=right,k=left; k<=right; k++) if (Compare::le(TempArray[index1], TempArray[index2])) Array[k] = TempArray[index1++]; else Array[k] = TempArray[index2--]; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 99 时间代价 „ 划分时间 „ 两个子序列的排序时间 „ 归并时间，n 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 100 „ T(1)=1 „ 归并排序总时间代价也为 „ Θ(nlog n) T n T n cn ( ) 2 ( / 2) = + 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 101 算法分析 „ 空间代价：Θ(n) „ 总时间代价：Θ(nlog n) „ 不依赖于原始数组的输入情况， 最大、最小以及平均时间代价均 为Θ(nlog n)。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 102 算法分析（续） „ 稳定 „ 优化： „ 同优化的快速排序一样，对基本 已排序序列直接插入排序 „ R.Sedgewick优化：归并时从两 端开始处理，向中间推进