分治法-归并排序

分治法

很多算法都使用了递归结构，通过递归来解决相互关联的问题。把一个规模很大的问题分解成几个相似的规模较小的子问题，然后通过解决小问题，递归解决大问题。

分治法主要是基于三个步骤来解决问题的：

• divide(分) 将问题分割为规模更小的子问题
• conquer(治) 将子问题各个击破
• combine(合) 合并子问题的解，得到原问题的解

归并排序

归并排序可以说是使用分治法思想的典型算法。

• divide 将n个元素的序列分成2个大小相同的子序列
• conquer 对2个子序列递归使用归并排序
• combine 合并两个子序列得到排好序的原序列

当子序列大小为1的时候，子序列有序，而归并排序的关键是合并两个已排序的子序列。我们通过调用MERGE（A,p,q,r）来实现，其中A是数组，其余的都是数组中的索引，而且p<=q<r。A[p,..q]和A[q+1,..r]是有序子数组，通过合并两个子数组使A[p,..,r]有序。

MERGE函数需要o(n)时间，其中n=r-q+1是需要排序的数组规模，下面是函数的伪代码：

MERGE(A,p,q,r)

n1 = q-p+1 
n2 = r-q
for i = 1 to n1
    L[i] = A[p+i-1]

for j = 1 to n2
    R[j] = A[q+i]

L[1+n1]=无穷大
R[1+n2]=无穷大

i=1
j=1

for k = p to r
    if L[i]<=R[j]
        A[k] = L[i]
        i++
    else 
        A[k]=R[j]
        j++

初始化：k=p，还没有向A中插入元素所有的数组都是有序的

循环中：假设L[i]<R[j]那么L[i]是未插入元素中的最小元素，在插入之前是有序的，所以插入之后任然有序。

结束：k=r+1 所有元素都已经按序插入到原数组中，数组有序。

我们可以把MERGE作为归并排序的递归函数。

主函数伪代码：

MERGE-SORT(A,p,r)
if p < r
    q=L(p+r)/2 //向下取整
    MERGE-SORT(A,p,q)
    MERGE-SORT(A,q+1,r)
    MERGE(A,p,q,r)

时间分析

T(n) 数据规模n的运行时间
D(n) 分解问题时间
C(n) 合并问题时间
我们把问题分解为a个子问题，每个问题的规模是n/b

可以构造一系列递归树，完全扩展的递归树有)层，每一层是cn，总代价是))，时间复杂度是。