算法导论三剑客之 分治算法 合并排序

 1 #include "iostream"
 2 #include "windows.h"
 3 #define MAX 0x7fffffff
 4 using namespace std;
 5 
 6 void merge(int s,int q,int e,int A[]){
 7     int i,j,k;
 8     int B[100],C[100];
 9     for(i=s;i<=q;i++)
10         B[i-s+1]=A[i];
11     for(j=q+1;j<=e;j++)
12         C[j-q]=A[j];
13     B[q-s+2]=C[e-q+1]=MAX;
14 
15     i=j=1;
16     k=s;
17     while(k<=e){
18         if(B[i]>=C[j]){
19             A[k]=C[j];
20             j++;
21         }
22         else{
23             A[k]=B[i];
24             i++;
25         }
26         k++;
27     }
28 
29 }
30 
31 
32 void merge_sort(int s,int e,int A[]){
33     if(e>s){
34         int q=(s+e)/2;
35         merge_sort(s,q,A);
36         merge_sort(q+1,e,A);
37         merge(s,q,e,A);
38     }
39 }
40 void main(){
41     int A[]={0,1,12,3,4,3,7,1,122};
42     merge_sort(1,8,A);
43     int i;
44     for(i=1;i<=8;i++){
45         cout<<A[i]<<" ";
46     }
47     cout<<endl;
48     getchar();
49 }