【递归】归并排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int a[10000],b[10000],n;
 5 
 6 
 7 void Merge(int left,int mid,int right)
 8 {
 9     int l=left,m=mid,k=left;
10     while(l<mid&&m<=right)
11     {
12         if(a[l]<a[m])
13         {
14             b[k]=a[l];
15             l++;
16         }else
17         {
18             b[k]=a[m];
19             m++;
20         }
21         k++;
22     }
23     if(l==mid)
24     {
25         while(m<=right){
26             b[k]=a[m];
27             k++;
28             m++;
29         }
30     }
31     if(m>right)
32     {
33         while(l<mid)
34         {
35             b[k]=a[l];
36             k++;
37             l++;
38         }
39     }
40 }
41 
42 void copy(int left,int right)
43 {
44     int l;
45     for(l=left;l<=right; l++)
46     {
47         a[l]=b[l];
48     }
49 }
50 
51 void MergeSort(int left,int right)
52 {
53     if(left<right)
54     {
55         if(right-left==1)
56         {
57             if(a[left]>a[right])
58             {
59                 int g=a[left];
60                 a[left]=a[right];
61                 a[right]=g;
62             }
63         }
64         else
65         {
66             int mid = left+(right-left)/2;
67             MergeSort(left,mid);
68             MergeSort(mid+1,right);
69             Merge(left,mid+1,right);
70             copy(left,right);
71         }
72     }
73 
74 }
75 
76 
77 int main()
78 {
79     scanf("%d",&n);
80     int i;
81     for(i=0; i<n; i++)
82     {
83         scanf("%d",&a[i]);
84     }
85     MergeSort(0,n-1);
86     for(i=0; i<n; i++)
87         printf("%d\n",a[i]);
88     return 0;
89 }