分治算法策略(4).doc

分治策略(四)归并排序【问题描述】 对一组无序的整数用归并法进行排序【输入】 两行，第一行为数列的总个数，第二行为待排序的数列【输出】一行，排序后的数列【样例输入】810 4 6 3 8 2 5 7【样例输出】2 3 4 5 6 7 8 10【问题分析】归并排序是利用归并技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序实际上就是二分法在排序中的应用。它的基本思想是：将待排序的数列分成两个小的数集，先对两个子数集进行排序，然后进行两个有序子集的合并，形成排序后的数列(称为序列)，而对子集的处理方法与刚才的处理方法是一致的，直到子集中只存在一个整数为止一结束分解。(详见图4-6)【程序分析(伪代码)】Procedure sort(e:arr;n:integer);对数组e中的n个元素进行排序if (n=2) then begin i=n div 2;j=n-i;令a包含e中的前i个元素；令b包含e中余下的j个元素；sort(a,i);sort(b,j);merge(a,b,e,i,j); 把a和b合并到eendelse 终止；procedure merge (a,b:arr;var e:arr;i,j:integer); var k,m,mb,p:integer;begin k:=1;m:=1;p:=0; while (k=i)and(m=j) do begin if (akm then for mb:=m to j do begin p:=p+l;ep:=bmb end else for mb:=k to i do begin p:=p+l;ep:=amb end;end;【参考程序】type arr=array1.100 of integer;var i,n:integer; e:arr;procedure merge (a,b:arr;var e:arr;i,j:integer); var k,m,mb,p:integer; begin k:=1;m:=1;p:=0; while (k=i)and(m=j) do begin if (akm then for mb:=m to j do begin p:=p+1;ep:=bmb end else for mb:=k to i do begin p:=p+1;ep:=amb end;end;Procedure sort(var e:arr;n:integer);对数组e中的n个元素进行排序 var i,ii,j,jj:integer;a,b:arr; begin if (n=2) then begin i:=n div 2; j:=n-i; for ii:=1 to i do aii:=eii;/令a包含e中的前i个元素； for jj:=1 to j do bjj:=ei+jj;/令b包含e中余下的j个元素； sort(a,i); sort(b,j); merge(a,b,e,i,j); 把a和b合并到e end else exit; end;begin readln(n); for i:=1 to n do read(ei); sort(e,n); for i:=1 to n do write(ei, );end.算法思考与改进：【改进一】按照下述过程对以上伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对A中的初始序列进行排序，并将所得到的排序序列归并到一个新数组B中，最后将它们复制到A中。mergesort( A:arr;left,right:integer);对A数组中从left到right元素进行排序begin if leftright then begin 至少两个元素 i:=(left + right) div 2: mergesort(a,left,i); mergesort(a,i+l,right); merge(a,b,left,i,right); 从a合并到b copy(b,a,left,right); 结果放回a end;end ;procedure merge (a,b:arr;left,i,right:integer); var k,m,mb,p,r1,r2:integer;begin k:=left;m:=i+1;r1:=i;r2:=right;p:=left; while (k=r1)and(m=r2) do begin if (akm then for mb:=m to r2 do begin p:=p+l;bp:=amb end else for mb:=k to r1 do begin p:=p+l;bp:=amb end;end;参考程序：program guibing;var a:array1.100 of integer; n,i:integer;procedure merge(left,mid,right:integer); var h,i,j,k:integer; b:array1.100 of integer;/思考，b数组定义在这里合适吗？ begin h:=left; i:=left; j:=mid+1; while (h=mid) and (j=right) do begin if (ahmid then for k:=j to right do begin bi:=ak; i:=i+1; end else for k:=h to mid do begin bi:=ak; i:=i+1; end; for k:=left to right do ak:=bk; end;procedure mergesort(left,right:integer); var mid:integer; begin if leftright then begin mid:=(left+right) div 2; mergesort(left,mid); mergesort(mid+1,right); merge(left,mid,right); end; end;begin read(n); for i:=1 to n do read(ai); mergesort(1,n); for i:=1 to n do write(ai:7);end.【改进二】仔细查看原有的序列,我们可以发现，其实也可以不需人为地分成两个部分，只要将序列从左往右扫描一下，就可以分成若干有序序列。 例如，元素序列4，8，3，7，1，5，6，2中就可以分成子序列4，8，3， 7，1，5，6和2，每个子序列都是有序的。分割子序列的标准是：若位置i的元素比位置i+l的元素大，则从位置i进行分割。然后再根据归并的算法进行归并运算。这种排序列被称为自然归并排序，它是基本归并排序的一种改进。 对于上面这个元素序，可以找到四个子序列，子序列1和子序列2归并可得3，4，7，8，子序列3和子序列4归并可得1，2，5，6，最后，