Merge

算法作用：一个数组a[0,…,p…,q…,r,…]，其中子数组a[p,..,q]和a[q+1,…,r]两个数组是升序的数组，通过merge算法将这两个数组合并变成一个升序的数组。

算法思想：将b[]矩阵作为缓冲矩阵，用s，t指向这两个子数组的首元素，然后一次循环比较两个数组的元素大小，将较小的元素赋值给数组b[]，直到两个子数组中的其中一个遍历完全。然后把未遍历完的子数组元素赋值给b[]。最后将b[]赋值给a[]。

注意事项：

• “ = =” 与“ = ” 号的区别！！！“ && ” 和“ & ”的区别！！！
• 定义一个int型大小为N的数组的时候，例如下面的第7行和第9行，必须声明b为int型的指针，然后指向的位置是一个(r-p+1)*sizeof(int)大小的存储空间，注意这个大小的表达方式，写成b = (int*)malloc(sizeof((r-p+1)*int));这样是不对的！
• 数组元素一定是从a[0]开始的，例如下面的例子中如果将12行改为k=p。由于b是一个（r-p+1）大小的数组，所以下面的b标号也就从p开始了，但是前面的0到p-1还是占着b的位置的。所以会造成溢出！
• 注意 ++ 和 = +1的区别！25行到38行的两种表达方式的区别！
• 对于以后要用到的数据，如果用途不同，要采用赋值的方法解决，比如下面的s，t，k的定义。
• 数组作为参数的传递，第4行和第57行的。

#include<stdio.h>
#include<malloc.h>

void merge(int a[], int p, int q, int r)
{
    int s,t,k;
    int *b;
    int i;
    b = (int*)malloc((r-p+1)*sizeof(int));
    s = p;
    t = q+1;
    k = 0;
    while ((s<=q)&&(t<=r))
        if(a[s]<=a[t])
            b[k++] = a[s++];
        else
            b[k++] = a[t++];
    if(s == q + 1)
        while (t<=r)
            b[k++] = a[t++];
    else
        while (s<=q)
            b[k++] = a[s++];
    k = 0;
    while (p<=r)
    {
        printf("%3d", b[k]);
        a[p++] = b[k++];
    }
/*
    while (p<=r)
    {
        a[p] = b[k];
        printf("%3d", b[k]);
        p = p + 1；
        k = k + 1；
    }
*/
    printf("\n");
}
int main()
{
    int N,i,p,q,r;
    int *a;
    printf("Please input the numbers of array:");
    scanf("%d", &N);
    a = (int* )malloc(N*sizeof(int));
    printf("Please input the array:");   //输入的时候注意要输入两个递增的子数列！
    for(i=0; i<N; i++)
        scanf("%d",&a[i]);
    printf("Please input the first begin number:");
    scanf("%d", &p);
    printf("Please input the first end number:");
    scanf("%d", &q);
    printf("Please input the second end number:");
    scanf("%d", &r);
    merge(a,p,q,r);
    for (i = 0; i < N; i++)
        printf("%3d",a[i]);
    return 0;
}