合并排序算法.doc

《合并排序算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是合并排序合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序递归合并排序#include　　template

2、T>voidMergeSort(Ta[],intleft,intright);　　templatevoidMerge(Tc[],Td[],intl,intm,intr);templatevoidCopy(Ta[],Tb[],intl,intr);　　voidmain()　　{　　intconstn(5);　　inta[n];　　cout<<"Input"<>a[i];　　　　MergeSort

3、(a,0,n-1);　　cout<<"Thesortedarrayis"<　　voidMergeSort(Ta[],intleft,intright)　　{　　if(left

4、ft,i,right);　　Copy(a,b,left,right);　　}　　}　　template　　voidMerge(Tc[],Td[],intl,intm,intr)　　{　　inti=l,j=m+1,k=l;　　while(i<=m&&j<=r)　　{　　if(c[i]<=c[j])d[k++]=c[i++];　　elsed[k++]=c[j++];　　}　　if(i>m)　　{　　for(intq=j;q<=r;q++)　　d[k++]=c[q];　　}　　else　　for(intq=i

5、;q<=m;q++)　　d[k++]=c[q];　　}　　template　　voidCopy(Ta[],Tb[],intl,intr)　　{　　for(inti=l;i<=r;i++)　　a[i]=b[i];}迭代合并排序#includevoidprintArray(int*head,intlen){printf("datas:");inti=1;for(i=1;i<=len-1;i++){printf("%d",head[i]);}printf("");}voidcopyA

6、rray(int*head,int*tmp,intlen){inti=0;for(i=0;i<=len;i++){head[i]=tmp[i];}}/****/voidMergeTwo(int*head,int*tmp,intl,intm,inth){printf("l:%dm=%dh=%d",l,m,h);inti=l,j=m+1,k=l;for(;i<=m&&j<=h;k++){if(head[i]<=head[j]){tmp[k]=head[i++];}else{tmp[k]=head[j++];}}wh

7、ile(i<=m){tmp[k++]=head[i++];}while(j<=h){tmp[k++]=head[j++];}}/****/voidMergeSortFlag(int*head,int*tmp,intlen,intflag){inti=1;intt;while(i<=(len-2*flag+1)){MergeTwo(head,tmp,i,i+flag-1,i+2*flag-1);i=i+2*flag;}printf("i=%d",i);if(i+flag-1

8、tmp,i,i+flag-1,len);}else{for(t=i;t<=len;t++){tmp[t]=head[t];}}printf("flag:%d",flag);printArray(tmp,len+1);copyArray(head,tmp,len);}/****/voidMergeSort(int*head,int*