分治法的归并算法

时间:2022-07-23 11:08:40

分治法下的归并算法(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 }

算法分析

  与递归算法相比较,在n大于30后,归并算法有着较为明显的优势。他的时间复杂度比递归的时间复杂度更低,所以在排序较多数据时,归并算法能取得较好的效果!

    递归算法:Θ(n) = (n^2)

    归并算法:Θ(n) = (nlgn)  //注意,这里的lgn是log2n的代表

  下面我们用一张图来说明其时间复杂度

分治法的归并算法

假设问题的个数正好是2的n次幂

那么一层一层分下来

第一层的总代价cn

第二层总代价c(n/2) +c(n/2) = cn

………

这样,每一层的总代价都是cn

那么一共有lgn层,再加上第一层

所以总代价即为:cn*lgn+cn = Θ(nlgn)

PS:即使问题的个数不是2的n次幂,也可使用这样的算法,这里只是为了方便讨论和理解