归并排序

 1 #include<iostream>
 2 using namespace std;
 3 int a[]={13,5,8,8,66,33,2,12,0,56,20};
 4 void merge_sort(int start,int mid ,int end){//结合并排序 
 5     int *tmp=new int[end-start+1];//开一段空间 
 6     int i=start;
 7     int j=mid+1;
 8     int k=0;
 9     while(i<=mid&&j<=end){//选取最小的放前面 
10         if(a[i]<a[j])
11             tmp[k++]=a[i++];
12         else
13             tmp[k++]=a[j++];    
14     }
15     while(i<=mid)//如果其中一列放完了，就把另一列的全放上去 
16         tmp[k++]=a[i++];
17     while(j<=end)
18         tmp[k++]=a[j++];
19     for(int i=0;i<k;i++)//把tmp里的放入数组a相应位置 
20         a[start+i]=tmp[i];    
21 }
22 void separation(int start,int end){//分离的操作 
23     if(start>=end)//终止条件 
24         return;
25     int mid=(start+end)/2;
26     separation(start,mid);//不停递归 
27     separation(mid+1,end);
28     merge_sort(start,mid,end);//分散到足够小后结合并排序 
29 }
30 int main(){
31     int len=sizeof(a)/sizeof(a[0]);
32     separation(0,len-1);
33     for(int i=0;i<len;i++)//输出 
34         printf("%d ",a[i]);
35     return 0;
36 }