分治法

我们可以选择使用的算法设计技术有很多。插入排序使用了增量方法。本节我们考查另一种称为“分治法”的设计方法。分治算法通过递归拆分问题，显著降低时间复杂度，是算法设计中的重要范式。

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

分治法通过下面的这些步骤解决问题:

分解(Divide): 将原问题划分为多个规模较小的子问题(通常与原问题结构相同)。
解决(Conquer): 递归地解决子问题。若子问题规模足够小，则直接求解²。
合并(Combine): 将子问题的解合并为原问题的解。

可以看出分治主张 “分而治之” 的哲学，形式上一般通过递归来解决问题，它的子问题是独立、不重叠的。

我们将用分治法来设计一个排序算法，该算法的最坏情况运行时间比插入排序要少得多。

归并排序

我们来看一个很早就接触过的主问题:

输入

$n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$

输出

输入数组的升序排列 $< a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'} >$ ，满足 $a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}$

对于这个问题，我们进行分割将数组分割成两个n/2的子数组(实际上，n/2会被截断小数部分，所以当n为奇数时，右半部分(right)会多出一个元素³)，然后对这两个子数组重复上面分割。不可分割时，需进行排序，然后合并已排序的数组。这是一个先自上而下分解问题，再**逐步回升(自底向上)**解决问题的过程。

实现1

pub fn realize<T: Ord + Clone>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return; // 基本情况: 数组长度为0或1时直接返回
    }

    let mid = arr.len() / 2;
    let mut left = arr[..mid].to_vec(); // 分割左半部分
    let mut right = arr[mid..].to_vec(); // 分割右半部分

    // 递归排序左右子数组
    merge_sort(&mut left);
    merge_sort(&mut right);

    // 合并排序后的左右子数组
    merge(arr, &left, &right);
}

// 合并两个有序数组的辅助函数
fn merge<T: Ord + Clone>(arr: &mut [T], left: &[T], right: &[T]) {
    let (mut i, mut j, mut k) = (0, 0, 0);

    // 比较左右子数组的元素，按顺序合并到原数组
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    // 处理剩余元素(左子数组或右子数组可能未完全合并)
    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

在合并两个有序数组中，由于两个数组都已排序，所以我们就要从中观察两个数字的首项，找到较小的项加入新数组，这个过程中保证了新数组有序。其中一个子数组全部排完后，直接将剩下的有序数组放入新数组。我们来观察一组输入:

1 2 4
3 7 8

它的变化过程是这样的:

1.
left: 2 4
right: 3 7 8
new: 1
2.
left: 4
right: 3 7 8
new: 1 2
3.
left: 4
right: 7 8
new: 1 2 3
4.
left: 
right: 7 8
new: 1 2 3 4
5. (将剩下数组放入)
left:
right:
new: 1 2 3 4 7 8

当然，这只是一种思维方式。实际的实现中，我们通常不改变左右数组，而是简单的通过一个索引来从中获取数据并模拟扔出数据的过程。这个过程需要遍历两个数组的所有元素，所以它是 $Θ (n)$ ⁴的。

《算法导论》中，将左右数组的最后一项设为 $\infty$ ，只需要遍历到 $\infty$ 就意味着其中一个数组已经遍历完，不需要像实现一一样检查剩余元素。这里用于简化边界条件的 $\infty$ 便是哨兵值。

哨兵(Sentinel) 是一种用于简化算法边界条件的编程技巧。它通常是一个特殊的值或节点，用于标记数据结构的边界，从而避免在循环或递归中频繁检查边界条件，提升代码的简洁性和效率。

在Rust我们做不到使用 $\infty$ ，哪怕用Default::default也会导致数据冲突(如数字0)，所以我们不采用哨兵值。如果你认为你的数据里不会产生0或-1这样的值，那加上哨兵值也是可取的。

练习与回答

试给出归并排序的循环不变式并证明。

循环不变式

在MERGE(辅助函数)过程的while i < left.len() && j < right.len()循环的每次迭代开始时，子数组 A[p..k-1](即arr) 包含 L[1..i-1] 和 R[1..j-1] (即 left 和 right)中的 k-p 个最小元素，并且 A[p..k-1] 是有序的。进而，L[i] 和 R[j] 是各自数组中未被复制回 A 的最小元素。

证明

初始化

在循环开始之前，k = p，因此A[p..k-1]是空的，即不包含任何元素。i = 1和j = 1，所以L[1..i-1]和R[1..j-1]也是空的。因此，A[p..k-1]包含0个最小元素，且是有序的。L[1]和R[1]分别是L和R中未被复制的最小元素(因为还没有任何元素被复制)。因此，初始化时循环不变式成立。

保持

假设在循环的某次迭代开始时，循环不变式成立。即A[p..k-1]包含L[1..i-1]和R[1..j-1]中的k-p个最小元素，且A[p..k-1]是有序的。L[i]和R[j]是各自数组中未被复制的最小元素。

在循环体中，我们比较L[i]和R[j]：

如果L[i] ≤ R[j]，则将L[i]复制到A[k]，然后i和k都加 1。
- 因为L[i]是L中未被复制的最小元素，且L[i] ≤ R[j]，所以L[i]是L和R中未被复制的最小元素。
- 将L[i]放入A[k]后，A[p..k]现在包含L[1..i]和R[1..j-1]中的 $k - p + 1$ 个最小元素，且是有序的。
- L[i+1]和R[j]现在是各自数组中未被复制的最小元素。
如果L[i] > R[j]，则将R[j]复制到A[k]，然后j和k都加 1。
- 类似地，R[j]是R中未被复制的最小元素，且R[j] < L[i]，所以R[j]是L和R中未被复制的最小元素。
- 将R[j]放入A[k]后，A[p..k]现在包含L[1..i-1]和R[1..j]中的 $k - p + 1$ 个最小元素，且是有序的。
- L[i]和R[j+1]现在是各自数组中未被复制的最小元素。

因此，在每次迭代后，循环不变式仍然成立。

终止

当循环终止时，k = r + 1。根据循环不变式，A[p..k-1]即A[p..r]包含L[1..i-1]和R[1..j-1]中的 $r - p + 1$ 个最小元素，且是有序的。因为L和R总共有 $n 1 + n 2 = r - p + 1$ 个元素，所以A[p..r]包含了L和R的所有元素，且是有序的。

递归(Recursion) 是算法设计中的一种重要技术，指函数或过程直接或间接调用自身来解决问题的方法。 ↩
这种可直接求解的边界叫做基线条件(Base Case)。如实现一的基本情况。 ↩
这意味着右数组有 $⌈ n ⌉$ 个元素，左数组有 $⌊ n ⌋$ 个元素。其中 $⌈ x ⌉$ 表示大于或等于 $x$ 的最小整数， $⌊ x ⌋$ 表示小于或等于 $x$ 的最大整数。 ↩
这只是辅助函数的时间复杂度，归并排序的实际复杂度在后面解答。 ↩

Keyboard shortcuts

算法学习