《数据结构（C语言描述）（第2版）》教学课件6-12归并排序2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：丁慧,归并排序,常州信息职业技术学院,02,07,（,1,）基本思想,：,将待排序的文件,R1.n,看作是,n,个长度为,1,的有序子文件，将这些子文件两两归并，直到得到一个长度为,n,的有序文件为止。,2,、 自底向上归并排序,归并排序,（,2,）排序方法,：,初始状态,：,n,个有序区,R1,，,R2,，,Rn,。,第,i,趟排序前状态,：,设第,i,趟排序时,区间长度为,length,，则各有序区为,R1. length,，,Rlength+1. 2*length,，,R2*length+1. 3*length,，。,排序方法,依次,对长度为,length,的两个相邻子文件,R,i,i+length-1,，,R,i+length, i+2*length-1,进行归并，如果最后还剩两个子文件，即,i+length-1n,，其中最后一个子文件长度小于,length,，将这两个子文件也归并，如果最后只剩一个子文件，即,i,n,且,i+length+1,n,，则该子文件轮空，无须归并。一趟归并结束将长度值,length,增加到,2*length,。,重复,进行第步，直到全部记录都在一个文件为止。,08,初始关键字,25 57 48 37 12 92 86,归并排序,第一趟归并,25 57 37 48 12 92 86,第二趟归并,25 37 48 57 12 86 92,第三趟归并,12 25 37 48 57 86 92,2,、 自底向上归并排序,09,（,3,）排序算法,：,void BottomUpMergeSort(SeqList R),自底向上归并排序,int length,i;,for(length=1;lengthn;length*=2), /,两两归并,for(i=1;i+2*length-1=n;i=i+2*length),Merge(R,i,i+length-1,i+2*length-1);/,归并长度为,length,的两个相邻子文件,if(i+length-1n) /,尚有两个子文件，其中后一个长度小于,length,Merge(R,i,i+length-1,n); /,归并最后两个子文件,归并排序,2,、 自底向上归并排序,10,（,4,）算法分析,：,时间性能,：,自底向上,归并排序每进行一次两两归并即完成一趟排序，所以共,进行,lgn,趟排序，每趟归并时间为,O(n),，时间复杂度为,O(nlgn),。,空间性能,：,辅助,空间为,O(n),，不是就地排序,。,稳定性,：,是,稳定,的排序方法。,归并排序,2,、 自底向上归并排序,THANKS,2016.9.18,