归并排序

 1 #include<iostream>
 2 using namespace std;
 3 int a[10001],r[10001],n,i;        //a是待排序数组，r是临时数组
 4 void mergesort(int s,int t)     //对[s,t]区间的无序数据进行归并排序
 5 {    
 6     int m,i,j,k;
 7     if(s==t)  
 8     return;             //若区间只有一个数据就不用排了
 9     m=(s+t)/2;                    //取区间的中点
10     mergesort(s,m);            //以中点二分，对左边了区间进行排序
11     mergesort(m+1,t);              //以中点二分，对右边了区间进行排序
12     i=s;                     //以下是一次归并（合并）操作 
13     j=m+1;
14     k=s;
15     while(i<=m&&j<=t)   //二个子序列从小大到合并，直到有一列结束
16     {  
17         if(a[i]<=a[j])   
18         {r[k]=a[i];
19         i++;k++;
20         }
21         else
22         {
23         r[k]=a[j];
24         j++;k++;
25         }
26     }
27     while(i<=m)//*把左边子序列剩余的元素接入进来*
28     {
29         r[k]=a[i];
30         i++;
31         k++;
32     }
33     while (j<=t)             //把右边子序列剩余的元素接入进来
34     {
35         r[k]=a[j];
36         j++;
37         k++; 
38     }
39     for(i=s;i<=t;i++)            //把合并后的有序数据重新放回a数组
40     a[i]=r[i];
41 }
42 int main()
43 {  
44     cin>>n;
45     for(i=1;i<=n ;i++)                   //读入n个待排序数据
46     cin>>a[i];
47     mergesort(1,n);        //对[1,n]区间的无序数据进行归并排序
48     for (i=1;i<=n;i++)                   //输出n个有序的数据
49     cout<<a[i]<<" " ;
50     cout<<endl;
51 }