归并排序

Posted on

MergeSort

算法形式

分治法：
对于每次递归的调用自身去解决相关问题的子问题的算法，均遵循了分治法的思想：将原问题分解为规模较小的子问题（子问题的形式应该类似于原问题），递归求解子问题，然后合并子问题的解，形成原问题的解

分治模式在每层递归是有三个步骤：

  • 分解
  • 解决
  • 合并

对于归并排序算法,当序列被分解为长度1时，递归开始回升，算法的关键在于合并两个已经排列好的序列，调用MERGE(A,p,q,r)来完成这个操作，其中A[p..q]和A[q+1..r]都分别排序好，合并两个数组得到A[p,r],该合并操作最多执行$r-p+1$次操作，因此需要$\Theta(n)$的时间
伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MERGE(A,p,q,r)
n1 = q-p+1
n2 = r-q
let L[1..n1+1] and R[1..n2+1] be new arrays
copy A[p..q],A[q+1..r] to L[1..n1],R[1..n2]
L[n1+1] = Max
R[n2+1] = Max
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++

这里有个小技巧，就是将每堆底部放一张哨兵牌，并将其设置为$\infty$,因此当一堆出现$\infty$牌时，不可能出现比它大的牌，于是形式上相当于将另一堆直接放置到输出堆

算法证明

循环不变式:$A[p..k-1]$按从小到大的顺序包含$L[1..n1+1]$和$R[1..n2+1]$中的k-p个最小元素，$L[i]$和$R[j]$是各自数组中未被复制回A数组的最小元素

  • 初始化：A数组为空，$L[1]$和$R[1]$都是各自数组的最小元素
  • 保持：假设$L[i] \le R[j]$,这时$A[p..k-1]$包含$k-p个$最小元素，将$L[i]$复制到$A[k],A[p..k]$包含$k-p+1个$元素，更新$k$和$i$，可见循环不变式依旧成立
  • 终止：$k=r+1$,$A[p..r]$即按从小到大排列，数组$L$和$R$只剩下哨兵没有被赋值会数组A

算法分析

  • 解决子问题需要$2T(n/2)$的运行时间
  • 合并一个n大小的数组需要$\Theta(n)$
  • 因此归并排序的最坏运行时间$T(n)=2T(n/2)+\Theta(n)(n>1)$

通过画递归树，每层的代价都是$cn$,总层数为$lgn+1$,总代价即为$cn(lgn+1)=cnlgn+cn$,忽略低阶项和常量$c$便得出$T(n)=\Theta(nlgn)$

源代码

习题解答

Ex2.3-3

当n刚好是2的幂时，用数学归纳法证明下列递归式的解是$T(n)=nlgn$，$T(n)=2T(n/2)+n(n=2^k,k>1)$
设$n=2^k$
当$n=2$时，$k=1$,$T(2)=2lg2=2$成立
当$n>2$时，假设$T(2^k)=2^klg2^k$成立
则$T(2^{k+1})=2T(2^{k+1}/2)+2^{k+1}=2^{k+1}lg2^{k+1}$
得证

Ex2.3-4

为插入排序的递归版本的最坏情况写一个递归式
$T(n)=T(n-1)+n-1(n>1)$

Ex2.3-5

为二分查找写递归的伪代码，并判断最坏情况的运行时间为$\Theta(lgn)$

1
2
3
4
5
6
7
8
binary_search(A,low,high,key)
mid=(low+high)/2
if(A[mid]=key)return mid
else if(A[mid]<key)
    binary_search(A,mid,high,key)
else if(A[mid]>key)
    binary_search(A,low,mid,key)
return null

利用与Ex2.3-3类似的数学归纳法可证明结论成立

算法改进

在归并算法中对小数组采用插入排序，当子问题足够小时，采用插入排序来使递归的叶变粗

  • 使用插入排序来排序长度为k的n/k个子表，然后使用标准合并机制来合并这些子表，最坏的情况是在$n/k\Theta(k^2)=\Theta(nk)$的时间内完成排序
  • 最坏的情况下能在$\Theta(nlg(n/k))$的时间内合并子表
  • 修改后的归并排序算法最坏运行时间为$\Theta(nk+nlg(n/k))$,并且$k<\Theta(lgn)$,否则增长率将超过原来的算法
  • 对于k的取值，因为我们选取插入算法是为了改善，所以原本应该使用归并算法的部分应有$c_1k^2<c_2klgk$,得到k的取值范围