下面这图展示了二路归并的过程
二路归并的核心代码是merge（）函数
它将2个分割的数组有序的合并在一起
如图：
在数组A中，
从p到q是一个数组，从q到r是另外一个数组
那么如何将这2个数组有序的合并在一起，组个新的数组A呢？
步骤：
第一步：开辟一个数组L，存放p到q之间（也就是需要归并的左边数组）的元素
第二部：开辟一个数组R，存放q到r之间（也就是需要归并的右边数组）的元素
第三步：2个数组的最后还要加一个无穷大的数（可以用0x7FFF表示），因此开辟的数组空间要多1字符个空间
第四步：L与R中的数字逐个比较，把较小的先放在数组A中（从数组A【0】开始存放，依次往后覆盖原来的数），然后较小的数组指针往后移动，指向下一位再和另外一个数组比较
- void Merge(int *A,int p,int q,int r)
- {
- int n1,n2,i,j,k,g;
- n1=q-p+1;
- n2=r-q;
- int *L,*R;
- L=(int *)malloc(sizeof(int)*(n1+1));
- R=(int *)malloc(sizeof(int)*(n2+1));
- L[n1]=0x7fff;
- R[n2]=0x7fff;
- g=0;
- for(i=p;i<=q;i++)
- {
- L[g]=A[i];
- g++;
- }
- g=0;
- for(i=q+1;i<=r;i++)
- {
- R[g]=A[i];
- g++;
- }
-
- j=k=0;
- for(i=p;i<=r;i++)
- {
- if(L[j]<R[k])
- {
- A[i]=L[j];
- j++;
- }
- else
- {
- A[i]=R[k];
- k++;
- }
- }
- }
完整代码：
- #include<iostream>
- using namespace std;
-
- void Merge(int *A,int p,int q,int r)
- {
- int n1,n2,i,j,k,g;
- n1=q-p+1;
- n2=r-q;
- int *L,*R;
- L=(int *)malloc(sizeof(int)*(n1+1));
- R=(int *)malloc(sizeof(int)*(n2+1));
- L[n1]=0x7fff;
- R[n2]=0x7fff;
- g=0;
- for(i=p;i<=q;i++)
- {
- L[g]=A[i];
- g++;
- }
- g=0;
- for(i=q+1;i<=r;i++)
- {
- R[g]=A[i];
- g++;
- }
-
- j=k=0;
- for(i=p;i<=r;i++)
- {
- if(L[j]<R[k])
- {
- A[i]=L[j];
- j++;
- }
- else
- {
- A[i]=R[k];
- k++;
- }
- }
- }
-
- void MergeSort(int *A,int p,int r)
- {
- int q;
- if(p<r)
- {
- q=(p+r)/2;
- MergeSort(A,p,q);
- MergeSort(A,q+1,r);
- Merge(A,p,q,r);
- }
- }
-
- void main()
- {
- int A[5]={5,3,4,23,11};
- MergeSort(A,0,4);
- for(int i=0;i<5;i++)
- cout<<A[i]<<endl;
- system("pause");
- }
二路归并排序（也叫合并排序）
原文：http://www.cnblogs.com/Ph-one/p/7359767.html
