0103设计算法-算法基础-算法导论第三版

我们可以选择使用的算法设计技术有很多。插入排序使用了增量方法：在排序子数组 $A[1\cdots j-1]$后，将单个元素 $A[j]$插入子数组的适当位置，产生排序好的子数组 $A[1\cdots j]$。

下面我们学习称为“分治法”的设计方法。

一、分治法

许多有用的算法在结构上是递归的：为了解决一个问题，算法一次或者多次调用其自身以解决紧密相关的若干子问题。

这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题的解，然后在合并这些子问题的解来建立原问题的解。

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

1. 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
2. 解决这些子问题，递归地求解各子问题。然后，若子问题的规模足够小，则直接求解。
3. 合并这些子问题的解成原问题的解。

归并排序算法完全遵循分治模式。直观上其操作如下：

• 分解：分解待排序的n个元素的序列成各具有$\frac{n}{2}$个元素的两个子序列。
• 解决：使用归并排序递归地排序两个子序列。
• 合并：合并两个已排序的子序列以产生已排序的答案。

递归终止条件：当待排序的序列长度为1，递归“开始回升”，长度为1的每个序列都已排好序。

归并排序算法的关键操作是“合并”步骤中两个已排序序列的合并。我们通过一个辅助过程MERGE(A,p,q,r)来完成合并，其中A是一个数组，p、q和r是数组的下标，满足$p\le q<r$。该过程假设子数组$A[p\cdots q]和A[q+1\cdots r]$以排好序。它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组$A[p\cdots r]$。

过程MERGE需要$O(n)$的时间，其中$n=r-p+1$是待合并元素的总和。为避免在每个基本步骤必须检查是否有堆为空，我们在每个堆的底部放置一个哨兵，它包含一个特殊的值，用于简化代码。这里我们使用$\infty$作为哨兵值，它不可能为较小的值，除非两个堆都已显露出其哨兵值。下面的伪代码实现MERGE

MERGE(A,p,q,r)
1  n1=q-r+1
2  n2=r-q
3  let L[1...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

我们需要证明第12~17行for循环的第一次迭代之前该循环不变式成立，该循环每次迭代保持该不变式，并且循环终止时，该不变式提供了一种有用的性质来证明正确性。

初始化：循环的第一次迭代之前，有$k=p$,所以子数组$A[p\cdots k-1]$为空。这个空的子数组包含L和R的$k=p=0$歌最小元素。又因为$i=j=1$，所以$L[i]和R[j]$都是各自所在数组中未被复制回数组A的最小元素。

保持：为了理解每次迭代都维持选好不变式，首选假设$L[i]\le R[j]$.这时，$L[i]$是未被复制回数组A的最小元素。因为$A[p\cdots k-1]$包含$k-p$个最小元素，所以在第14行将$L[i]$复制到$A[k]$之后，子数组$A[p\cdots k]$将包含$k-p+1$个最小子元素。增加k的值（在for循环中更新）和$i$的值后，为下次迭代重新建立了该循环不变式。反之，若$L[i]>R[j]$，则第16~17行执行适当的操作来维持该循环不变式。

终止：终止时，$k=r+1$。根据循环不变式，子数组$A[p\cdots k-1]$就是$A[p\cdots r]$且按从小到大的顺序包含$L[1\cdots n1+1]和R[1\cdots n2+1]$中的$k-p=r-p+1$个最小的元素数组L和R一起包含$n1+n2+2=r-p+3$个元素。处两个最大的元素以为，其他所有元素都已被复制回数组A，这两个最大的元素是哨兵。

过程MERGE的运行时间是$O(n)，其中n=r-p+1$。第1-3行和第8-11行中的每行都需要常量时间，第4-7行的for循环需要$O(n1+n2)=O(n)$的时间，第12-17行的for循环有n次迭代，每次迭代需要常量时间。

现在我们keyiBaby过程MERGE做为归并排序的一个子程序来用。下面的过程MERGE-SORT(A,p,r)排序子数组$A[p\cdots r]$中的元素。若$p\ge r$,则该数组最多有1个元素，所以已经排好序。否则，分解步骤简单地计算一个下标q，将$A[p\cdots r]$分解成两个子数组$A[p\cdots q]和A[q+1\cdots r]$，前者包含$\lceil \frac{n}{2}\rceil$个元素，后者包含$\lceil \frac{n}{2}\rceil$个元素。

MERGE-SORT(A,p,r)
1  if p < r
2    q=floor((p+r)/2)
3    MERGE-SORT(A,p,q)
4    MERGE_SORT(A,q+1,r)
5    MERGE(A,p,q,r)

为了排序整个序列$A(A[1],A[2],\cdots ,A[n])$，我们执行初始调用MERGE-SORT(A,1,A.length)，这里再次有$A.length=n$。下图索命了当n位2的幂时该操作的过程。

算法分为分解和合并两部分。

分解：把长度为n的序列分解为$\frac{n}{2}$的两个子序列，在把长度为$\frac{n}{2}$的子序列分解为$\frac{n}{4}$的子序列，直至子序列长度为1.

合并：合并只含1项的序列形成长度为2的排好序的序列，合并长度为2的序列形成长度为4的排好序的序列，依此下去，直到长度为$\frac{n}{2}$的两个序列被合并最终成都为n的排好序的序列。

二、分析分治算法

当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间，该方程根据在较小输入上的运行时间来描述在规模为n的问题上的总运行时间。然后，我们可以使用数学工具来求解该递归式并给出算法性能的界。

分治算法运行时间的递归式来自基本模式的三个步骤。如前所述，我们假设$T(n)$是规模为n的一个问题的运行时间。若问题规模足够小，如对某个常量$c,n\le c$，则直接求解需要常量时间，我们将其写作$O(1)$。假设把原问题分解为$a$个子问题，没个子问题的规模是原问题的$\frac{1}{b}$为了求解一个规模$\frac{n}{b}$的子问题，需要$T(\frac{n}{b})$的时间，所以需要$aT(\frac{n}{b})$的时间求解a个子问题。如果分解问题成子问题需要时间D(n)，合并子问题的解成原问题的解需要时间为C(n),那么得到递归式
$$T(n)=\{\begin{array}{l}O(1),若n\le c\\ aT(\frac{n}{b})+D(n)+C(n)其他\end{array}$$

归并排序算法的分析

虽然MERGE-SORT的伪代码在运算的数量不是偶数时也能正常工作，但是，如果假定原问题规模是2的幂，那么基于递归式的分析将被简化。在第4章，我们将看到这个假设不影响递归式解的增长量级。

下面我们分析建立归并排序n个数的最坏情况下的运行时间T(n)的递归式。归并排序一个元素需要长时间。当有$n>1$个元素时，我们分解运行时间如下：

分解:分解步骤仅仅计算子数组的中间位置，需要常量时间，因此，D(n)=O(1)。

解决：我们递归求解两个规模为$\frac{n}{2}$的子问题，运行时间为$2T(\frac{n}{2})$

合并: 在一个具有n个元素的子数组上过程MERGE需要O(n)的时间，所以C(n)=O(n)。

把分析结果带入上述递归式，有
$$T(n)=\{\begin{array}{l}O(1),若n=1\\ 2T(\frac{n}{2})+O(n)，n>1\end{array}$$
在第4章，我们将看到“主定理”，可以用改定理证明$T(n)=O(n\lg n),起咋\lg n代表{\log }_{2}n$。

因为对数函数比任何线性函数增长要慢，所以对足够大的输入，在最坏情况下，运行时间$O(n\lg n)$的归并排序将优于运行时间诶$O(n^2)$的插入排序。

算法实现及优化（在输入规模小于某个阈值时，使用插入排序）见下面链接2.

结语

欢迎小伙伴一起学习交流，需要啥工具或者有啥问题随时联系我。

❓QQ:806797785

⭐️源代码地址：https://gitee.com/gaogzhen/algorithm

[1]算法导论(原书第三版)/(美)科尔曼(Cormen, T.H.)等著;殷建平等译 [M].北京:机械工业出版社,2013.1(2021.1重印).p16-22

[2]归并排序-排序-算法第四版[CP/OL]