分治法下的归并算法(merge sort)
分支模式的三个步骤:
分解:将原问题分解为若干个子问题,子问题为原问题规模较小的问题
解决:递归求解子问题,若足够小,直接求解
合并:将子问题的解合并为原问题的解
归并算法(merge sort)
分解:分解待排序的n个元素的序列成各具n/2个元素的子序列
解决:使用归并算法解决两个子序列的排序
合并:合并两个已排序的子序列
伪代码实现归并的过程
MERGE(A,p,q,r) //A代表一个数组,pqr分别代表下标(p<=q<r) 1 n1 = q-p+1 2 n2 = r-q 3 let L[1,2…,n1+1] and R[1,…n2+1] be new arrays 4 for i = 1 to n1 5 L[i]=A[p+i-1] 6 for j=1 to n2 7 R[j]=A[q+j] 8 L[n1+1]=∞ 9 R[n2+1]=∞ 10 i=1 11 j=1 12 for k = p to r 13 if L[i] <= R[j] 14 A[k]=L[i] 15 i = i+1 16 else A[k] =R[j] 17 j=j+1
这里是归并过程的伪代码,归并过程作为本算法的另一个核心,其代码过程也充分体现了排序的过程
总程序
MERGE-SORT(A,p,r) 1 if p<r 2 q=(p+r)/2 3 MERGE-SORT(A,p,q) 4 MERGE-SORT(A,q+1,r) 5 MERGE(A,p,q,r)
这里的总程序运用了递归的思想,这样达到了将程序分解的目的,同时也体现了分治的思想
c++语言实现函数(仅有函数部分,未经过测试)
1 const int maxn= 100; 2 const int max = 100000; 3 int * Merge(int * &A,int p,int q,int r) 4 { 5 int L[maxn]={0}; 6 int R[maxn]={0}; 7 int n1=q-p+1; 8 int n2=r-q; 9 for(int i=0;i<n1;i++) 10 L[i]=A[p+i-1]; 11 for(int j=0;j<r;j++) 12 R[j]=A[q+j]; 13 L[n1+1]=max; 14 R[n2+1]=max; 15 int a=1,b=1; 16 for(int i=p;i<r;i++) 17 { 18 if(L[a]<=R[b]) 19 { 20 A[i]=L[a]; 21 a++; 22 } 23 else 24 { 25 A[i]=R[b]; 26 b++; 27 } 28 } 29 return A; 30 } 31 32 void MergeSort(int * &A,int p,int r) 33 { 34 if(p<r) 35 { 36 int q=(p+r)/2; 37 MergeSort(A,p,q); 38 MergeSort(A,q+1,r); 39 Merge(A,p,q,r); 40 } 41 }