首页 > 代码库 > 算法导论三剑客之 分治算法 合并排序

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

 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 }