Manchester- 数据结构-归并排序

解题思路:
详解见1169题

参考代码:

#include<stdio.h>
#include<malloc.h>
#include<math.h>
void input(int *A,int n);
void output(int *A,int n);
void Mesort(int *A,int *B,int left,int right);
void Merge(int *A,int *B,int left,int middle,int right);
void copy(int *A,int *B,int left,int right);
/*--------------------------------------------------------*/
int main()
{
    int *A,*B;
    int n;
 while(scanf("%d",&n)!=EOF&&n!=0)
     {
         A=(int *)malloc(n*sizeof(int));
         B=(int *)malloc(n*sizeof(int));
         input(A,n);
         Mesort(A,B,0,n-1);
         output(A,n);
         free(A);
         free(B);
     }
return 0;


}
/*--------------------------------------------------------*/
void Mesort(int *A,int *B,int left,int right)
{
 if(left<right)
 {
    int i=(left+right)/2;
      Mesort(A,B,left,i);
      Mesort(A,B,i+1 ,right);
      Merge(A,B,left,i,right);
 copy(A,B,left,right);
 }
}
/*--------------------------------------------------------*/
void Merge(int *A,int *B,int left,int middle,int right)
{
int  i=left,j=middle+1,k=left;

while((i<=middle)&&(j<=right))
{
    if(A[i]<=A[j])
      B[k++]=A[i++];
     else
      B[k++]=A[j++];
}

if(i>middle)
    for(int q=j;q<=right;q++)
       B[k++]=A[q];
else
    for(int q=i;q<=middle;q++)
       B[k++]=A[q];

}
/*--------------------------------------------------------*/
void copy(int *A,int *B,int left,int right)
{
   for(;left<=right;left++)
       A[left]=B[left];
}
/*-------------------------*/
void input(int *A,int n)
{
   for(int i=0;i<n;i++)
      scanf("%d",&A[i]);
}
/*-------------------------*/
void output(int *A,int n)
{
   for(int i=0;i<n-1;i++)
      printf("%d ",A[i]);
      printf("%d\n",A[n-1]);
}

别忘点赞哦-.-