#include <stdio.h>
#include <stdlib.h>
void Merge(int a[],int p,int q,int r){
int i,j,k,n1,n2;
int * front,* back;
n1=q-p+1; //前一部分长度
n2=r-q; //后一部分长度
front = (int *)malloc(n1*sizeof(int)); //申请两个空间来存放拍好的数组
back = (int *)malloc(n2*sizeof(int));
for(i = 0;i<n1;i++){
front[i] = a[p+i];
}
for(i = 0;i<n2;i++){
back[i] = a[q+i+1];
}
//将元素合并
i=0;
j=0;
k=p;
while(i<n1&&j<n2){
if(front[i]<back[j]){
a[k++] = front[i++];
}
else{
a[k++] = back[j++];
}
}
//将剩余元素合并
while(i<n1){
a[k++] = front[i++];
}
while(j<n2){
a[k++] = back[j++];
}
}
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); //将两个部分合并
}
}
int main(){
int *a,n,i;
printf("请输入数组长度 n =");
scanf("%d",&n);
a= (int *)malloc(n*sizeof(int));
printf("输入数组:");
for( i=0;i<n;i++){
scanf("%d",&a[i]);
}
MergeSort(a,0,7); //合并结果
for( i=0;i<8;i++){
printf("%5d",a[i]);
}
printf("\n");
return 0;
}
归并排序
原文：http://blog.51cto.com/13645380/2108293
