数据结构-从概念到C++实现（第4版）课件 7-5归并排序

7-5归并排序v第七章排序技术学什么？二路归并排序的递归实现二路归并排序的非递归实现提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-5-1二路归并排序的递归实现v第七章排序技术基本思想二路归并排序的基本思想：将待排序序列划分为两个长度相等的子序列，分别对这两个子序列进行排序，得到两个有序子序列，再将这两个有序子序列合并成一个有序序列。r1rn/2…rn…rn/2+1划分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤运行实例2420101812待排序序列16划分242010181216分别排序101224161820合并101216182024一次合并：合并两个相邻的有序子序列20254050152130合并可以就地进行吗？ijk

temp[]15

算法描述：while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}first1last1last1+1last2data[]关键问题如何表示两个相邻的子序列？某个子序列比较完毕，做什么？算法描述：while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];202130

4050

算法实现voidSort::Merge(intfirst1,intlast1,intlast2){int*temp=newint[length];inti=first1,j=last1+1,k=first1;while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];for(i=first1;i<=last2;i++)data[i]=temp[i];delete[]temp;}递归算法voidSort::MergeSortRecusion(intfirst,intlast){if(first==last)return;else{intmid=(first+last)/2;MergeSort1(first,mid);MergeSort1(mid+1,last);Merge(first,mid,last);}}r1rn/2…rn…rn/2+1划分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤7-5-2

二路归并排序的非递归实现v第七章排序技术执行过程252040153010182025251540203010181540103018待排序序列第一趟归并结果第二趟归并结果第三趟归并结果1520254010183010151820253040构造初始有序子序列子序列长度有什么规律？在一趟归并中有几种情况？一趟归并设i

指向待归并序列的第一个记录，归并的步长是2h情况1：i+2h≤n，则相邻两个有序子序列的长度均为hihhi+2hnwhile(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}算法描述：voidSort::Merge(intfirst1,intlast1,intlast2)子序列长度有什么规律？在一趟归并中有几种情况？情况2：i+h＜n，则相邻有序子序列一个长度为h，另一个长度小于hif(i+h<length)

Merge(i,i+h-1,length-1);算法描述：hii+hn<h一趟归并设i

指向待归并序列的第一个记录，归并的步长是2h子序列长度有什么规律？在一趟归并中有几种情况？voidSort::Merge(intfirst1,intlast1,intlast2)情况3：i

+h≥

n，则表明只剩下一个有序子序列算法实现voidSort::MergePass(inth){inti=0;while(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}if(i+h<length)

Merge(i,i+h-1,length-1);}如何控制二路归并的结束？子序列长度有什么规律？voidSort::MergeSort(){inth=1;while(h<length){MergePass(h);h=2*h;}}25204015202525154020154015202540时间性能执行趟数：log2n每一趟：将记录扫描一遍，O(n)最好、最坏、平均情况：O(nlog2n)二路归并执行多少趟？每一趟的时间性能是多少？空间性能：合并不能就地进行，O(n)稳定性：稳定如果将判断条件改为(r[i]<r[j])，仍然是稳定的吗？w