C语言实现归并排序

 1 #include<stdio.h>
 2 
 3 #define MAXN 100
 4 //A[p,q] A[q+1,r]是两个有序数组，想办法把他们结合成一个有序数组
 5 void merge(int A[],int p,int q,int r){
 6     int n=0;
 7     int i=p;
 8     int j=q+1;
 9     int tmp[MAXN];
10     while(i<=q&&j<=r){
11         if(A[i]<=A[j])
12             tmp[n++]=A[i++];
13         else
14             tmp[n++]=A[j++];
15     }
16     while(i<=q)
17         tmp[n++]=A[i++];
18     while(j<=r)
19         tmp[n++]=A[j++];
20     int k;
21     for(k=p;k<p+n;k++)
22         A[k]=tmp[k-p];
23 }
24 
25 //归并排序主体
26 void merge_sort(int A[],int p,int r){
27     if(p<r){
28         int q=(p+r)/2;
29         merge_sort(A,p,q);
30         merge_sort(A,q+1,r);
31         merge(A,p,q,r);
32 }
33 }
34 
35 int main(){
36     int A[]={2,56,3,7,86,1,6,43,12};
37     merge_sort(A,0,8);
38     int k;
39     for(k=0;k<=8;k++)
40     printf("%d ",A[k]);
41     printf("
");
42     return 0;
43 }