算法导论 2.3-2习题解答

#include <iostream>
//#include <stdlib.h>
#include <new>
using namespace std;

void Merge(int *,int ,int,int );
void Merge_Sort(int *,int ,int );
void PrintArray(int *,int );

int main ()
{
    int A[]= {2,4,5,7,1,2,3,6};
    PrintArray(A,sizeof(A)/sizeof(int));
    Merge_Sort(A,1,8);
    PrintArray(A,sizeof(A)/sizeof(int));
    return 0;
}

void PrintArray(int *head,int len)
{
    cout<<(" datas:")<<endl;
    int i=0;
    for(i=0; i<=len-1; i++) {
        cout<< head[i] ;
    }
    cout<<endl;
}

void Merge_Sort(int *A,int p, int r)
{
    int q;
    if (p<r) {
        q=(p+r)/2;
        Merge_Sort(A,p,q);
        Merge_Sort(A,q+1,r);
        Merge(A,p,q,r);
    }
}

void Merge(int *A,int p,int q,int r)
{
    int n1=q-p+1;
    int n2=r-q;
    int *L= new int[n1];
    int *R= new int[n2];

    for(int i=0; i<n1; i++) {
        L[i]=A[p+i-1];
    }
    for(int j=0; j<n2; j++) {
        R[j]=A[q+j];
    }

    int i=0;
    int j=0;
    int k=p-1;
    while((i<=n1-1)&&(j<=n2-1)) {
        if(L[i]<=R[j]) {
            A[k]=L[i];
            i++;
        } else {
            A[k]=R[j];
            j++;
        }
        k++;
    }
    while (i<n1-1) {
        A[k]=L[i];
        i++;
        k++;
    }
    while (j<n2-1) {
        A[k]=R[j];
        i++;
        j++;
    }
    delete []L;
    delete []R;
}