优化的快速排序 plate <class Record class Compare> id ImprovedQuick Sorter<Record, Compare> 74.2归并排序 oSortRecord-Array r int left, int right) Aray[]为待排序数组,i分别为数组两端 if (right < left) return 算法思想 /长度小于等于值(16最住停止分割跳出递归 if (right-left+1> THRESHOLD)t 简单地将原始序列划分为两个子 int pivot= SelectPivot( left, right);//选轴值 序列 swap( Array, pivot, right);//轴值放在数组尾 pivot= Partition(Aray,left, right);//分割 分别对每个子序列递归排序 /对轴值左右分别进行快速排序 最后将排好序的子序列合并为一 Sort(Array, left, pivot-1 rray, pivot +1, right 个有序序列,即归并过程 大▲张铭写 北大单张铭写 叔新有,命邮 归并思想 2534453278122964) 两路归并排序 25344532)078122964) template <dass Record, class Compare> //两路归并排序类 34)3245(1278)(2964) TempEra int re irt yight nt middle) 12252932344564 北真大脆张写 真大影张帖写 叔新有,量究 template <class Record, class Compare> oid Twoway Sorter<Record, Compare> d Array l, Record TempArray [,int left, 归并函数 Ary为待排序散组,left,rght分别为数組两端 如果序列中只有0或1个记录,就不用排序 template <class record, class Compare> (left< right)t void //从中间划分为两个子序列 TwoWay Merge Sorter <Record, compare> 则左边已半进行趣出1)/2 Merge ( Record Arrayal Record TempArrayint left int right int middle) //对右边一半进行递归 //归并过程 //将数组暂存入临时数组 (Array, TempArray, middle+1, right); /进行归并 for (int j=left; j<=right; j++) Age(Array, TempArray, left, right, middle); TempArray u] Array ji 北真大学张铭编写 聊张帖写 权新有,究 1515 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 85 优化的快速排序 template <class Record,class Compare> Void ImprovedQuickSorter<Record,Compare>:: DoSort(Record Array[], int left,int right) { //Array[]为待排序数组，i,j分别为数组两端 if (right <= left) return; //长度小于等于阈值(16最佳),停止分割跳出递归 if (right-left+1 > THRESHOLD){ int pivot = SelectPivot(left, right); //选轴值 swap(Array, pivot, right); // 轴值放在数组尾 pivot = Partition(Array, left, right); // 分割 //对轴值左右分别进行快速排序 DoSort(Array, left, pivot-1); DoSort(Array, pivot+1, right); } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 86 7.4.2 归并排序 „ 算法思想 „ 简单地将原始序列划分为两个子 序列 „ 分别对每个子序列递归排序 „ 最后将排好序的子序列合并为一 个有序序列，即归并过程 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 87 (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)(32 45)(12 78)(29 64) (25 32 34 45)(12 29 64 78) (12 25 29 32 34 45 64 78) 先划分再归并 归并思想 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 88 两路归并排序 template <class Record,class Compare> class TwoWayMergeSorter: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 89 template <class Record,class Compare> void TwoWayMergeSorter<Record,Compare>:: Sort(Record Array[], Record TempArray[],int left, int right) { //Array为待排序数组，left，right分别为数组两端 // 如果序列中只有0或1个记录，就不用排序 if (left < right) { //从中间划分为两个子序列 int middle=(left+right)/2; //对左边一半进行递归 Sort(Array, TempArray,left,middle); //对右边一半进行递归 Sort(Array, TempArray,middle+1,right); // 进行归并 Merge(Array, TempArray,left,right,middle); } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 90 归并函数 template <class Record,class Compare> void TwoWayMergeSorter<Record,Compare>:: Merge(Record Array[], Record TempArray[],int left,int right,int middle) { //归并过程 // 将数组暂存入临时数组 for (int j=left; j<=right; j++) TempArray[j] = Array[j];