2.3 设计算法

- · -

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

本节我们考查另一种称为“合治法”的设计方法。第 4 章将更深入地探究该方法。我们将用分法法来设计一个排序算法，该算法的最坏情况运行时间比插入排序要少得多。分治算法的优点之一是，通过使用第 4 章介绍的技术往往很容易确定其运行时间。

2.3.1 分治法

许多有用的算法在结构上是递归的：为了解决给定的问题，算法一次或多次递归地调用其自身解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

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

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

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

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

当待排序的序列长度为 1 时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为 1 的每个子序列都已经排序好。

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

过程 $MERGE$ 需要 $\theta(n)$ 的时间，其中 $n=r-p+1$ 是待合并元素的总数。它按以下方式工作。

---

未完待续