分治算法策略(4)

《分治算法策略(4)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分治策略(四)归并排序【问题描述】对一组无序的整数用归并法进行排序【输入】两行，第一行为数列的总个数，第二行为待排序的数列【输出】一行，排序后的数列【样例输入】8104638257【样例输出】234567810【问题分析】归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序实际上就是二分法在排序中的应用。它的基本思想是：将待排序的数列分成两个小的数集，先对两个子数集进行排序，然后进行两个有序子集的合并，形成排序后的数列(称为序列)，而对子集的处理方法与刚才的处理方

2、法是一致的，直到子集中只存在一个整数为止一结束分解。(详见图4-6)【程序分析(伪代码)】Proceduresort(e:arr;n:integer);{对数组e中的n个元素进行排序}if(n>=2)thenbegini=ndiv2;j=n-i;令a包含e中的前i个元素；令b包含e中余下的j个元素；sort(a,i);sort(b,j);merge(a,b,e,i,j);{把a和b合并到e}endelse终止；proceduremerge(a,b:arr;vare:arr;i,j:integer);vark,

3、,m,mb,p:integer;begink:=1;m:=1;p:=0;while(k<=i)and(m<=j)dobeginif(a[k]<=b[m])thenbeginp:=p+l;e[p]:=a[k];k:=k+lendelsebeginp:=p+l;e[p]:=b[m];m:=m+lend;end;ifk>mthenformb:=mtojdobeginp:=p+l;e[p]:=b[mb]endelseformb:=ktoidobeginp:=p+l;e[p]:=a[mb]end;end;【参考程序】t

4、ypearr=array[1..100]ofinteger;vari,n:integer;e:arr;proceduremerge(a,b:arr;vare:arr;i,j:integer);vark,m,mb,p:integer;begink:=1;m:=1;p:=0;while(k<=i)and(m<=j)dobeginif(a[k]<=b[m])thenbeginp:=p+1;e[p]:=a[k];k:=k+1endelsebeginp:=p+1;e[p]:=b[m];m:=m+1end;end;ifk

5、>mthenformb:=mtojdobeginp:=p+1;e[p]:=b[mb]endelseformb:=ktoidobeginp:=p+1;e[p]:=a[mb]end;end;Proceduresort(vare:arr;n:integer);{对数组e中的n个元素进行排序}vari,ii,j,jj:integer;a,b:arr;beginif(n>=2)thenbegini:=ndiv2;j:=n-i;forii:=1toidoa[ii]:=e[ii];//令a包含e中的前i个元素；forjj:

6、=1tojdob[jj]:=e[i+jj];//令b包含e中余下的j个元素；sort(a,i);sort(b,j);merge(a,b,e,i,j);{把a和b合并到e}endelseexit;end;beginreadln(n);fori:=1tondoread(e[i]);sort(e,n);fori:=1tondowrite(e[i],'');end.算法思考与改进：【改进一】按照下述过程对以上伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E

7、中保持两个子集合的左右边界即可。接下来对A中的初始序列进行排序，并将所得到的排序序列归并到一个新数组B中，最后将它们复制到A中。mergesort(A:arr;left,right:integer);{对A数组中从left到right元素进行排序}beginifleft

8、(b,a,left,right);{结果放回a}end;end;proceduremerge(a,b:arr;left,i,right:integer);vark,m,mb,p,r1,r2:integer;begink:=left;m:=i+1;r1:=i;r2:=right;p:=left;while(k<=r1)and(m<=r2)dobeginif(a[k]<=a[m])thenbeginp: