,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,归并排序,归并排序,归并排序,“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。,归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新,利用归并的思想实现排序,假设初始序列含有,n,个记录，则可看成是,n,个有序的子序列，每个子序列的长度为,1,，然后两两归并，得到,n/2,个长度为,2,或,1,的有序子序列；再两两归并，,，如此重复，直至得到一个长度为,n,的有序序列为止，这种排序方法称为,2-,路归并排序。,利用归并的思想实现排序假设初始序列含有n个记录，则可看成是n,例题,初始关键字：,49 38 65 97 76 13 27,一趟归并后：,38 49 65 97 13 76 27,二趟归并后：,38 49 65 97 13 27 76,三趟归并后：,13 27 38 49 65 76 97,例题初始关键字：49 38 65 97,算法思想,2-,路归并排序将,Rlow.high,中的记录归并排序后放入,Tlow.high,中。当序列长度等于,1,时，递归结束，否则：,（,1,）将当前序列一分为二，求出分裂点,mid=(low+high)/2;,（,2,）对子序列,Rlow.mid,递归，进行归并排序，结果放入,Slow.mid,中；,算法思想2-路归并排序将Rlow.high中的记录归并,算法思想,（,3,）对子序列,Rmid+1.high,递归，进行归并排序，结果放入,Smid+1.high,中；,（,4,）调用算法,Merge,，将有序的两个子序列,Slow.mid,和,Smid+1.high,归并为一个有序的序列,Tlow.high,。,算法思想（3）对子序列Rmid+1.high递归，进行,算法描述,void Msort(RedType R,RedType&T,int s,int t),/,将,Rs.t,归并排序为,Ts.t,if(s=t)Ts=Rs;,else m=(s+t)/2;,/,将,Rs.t,平分为,Rs.m,和,Rm+1.t,Msort(R,TR2,s,m);,/,递归地将,Rs.m,归并为有序的,TR2s.m,Msort(R,TR2,m+1,t);,/,递归地,Rm+1.t,归并为有序的,TR2m+1.t,Merge(TR2,T,s,m,t);,/,将,TR2s.m,和,TR2m+1.t,归并到,Ts.t,/Msort,算法描述void Msort(RedType R,算法描述,void MergeSort(SqList&L),/,对顺序表,L,作,2-,路归并排序,MSort(L.r,L.r,1,L.length);,/MergeSort,算法描述,将两个有序表归并为一个新的有序表的算法,void,Merge(RedType R,RedType,&,T,int,i,int,m,int,n),/,将有序的记录序列,Ri.m,和,Rm+1.n,归并为有序的记录序列,Ti.n,int j,k;,for(j=m+1,k=i;i=m +k),/,将,SR,中记录由小到大地并入,TR,if LQ(SRi.key,SRj.key)TRk=SRi+;,else TRk=SRj+;,if(i=m)/TRk.n=SRi.m;,将剩余的,SRi.m,复制到,TR,while(k=n,if(j=n)/,将剩余的,SRj.n,复制到,TR,while(k=n,/Merge,将两个有序表归并为一个新的有序表的算法void Merge,例 题,52,23,80,36,68,14 (s=1,t=6),52,23,80,36,68,14,52,23,80,52,23,52,23,52,80,36,68,14,36,68,36,68,14,36,68,14,23,36,52,68,80,23,例 题52,23,80,36,68,算法的效率,时间复杂度方面,，由于每趟归并的时间复杂度,O(n),，而对于有,n,个记录的序列来说，一共需要进行,log,2,n,趟归并。因此归并排序的时间复杂度是,O(n log,2,n),。,空间复杂度方面,，用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为,O(n),。,算法的效率时间复杂度方面，由于每趟归并的时间复杂度O(n)，,总 结,归并排序很显然是一种稳定的排序方法。,它也可用于链式存储结构存储的记录序列，并且不需要辅助的记录存储空间，但递归实现时仍然需要开辟相应的递归工作栈。,总 结归并排序很显然是一种稳定的排序方法。,