分治法

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

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

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

分解(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)会多出一个元素³), 然后对这两个子数组重复上面分割. 不可分割时, 需进行排序, 然后合并已排序的数组. 这是一个先自上而下分解问题, 再 逐步回升(自底向上) 解决问题的过程.

MERGE-SORT

#![allow(unused)]
fn main() {
pub fn merge_sort<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

它的变化过程是这样的:

flowchart LR
    step1["步骤1<br/>Left: 2 4<br/>Right: 3 7 8<br/>New: 1"] --> step2
    step2["步骤2<br/>Left: 4<br/>Right: 3 7 8<br/>New: 1 2"] --> step3
    step3["步骤3<br/>Left: 4<br/>Right: 7 8<br/>New: 1 2 3"] --> step4
    step4["步骤4<br/>Left: <br/>Right: 7 8<br/>New: 1 2 3 4"] --> step5
    step5["步骤5<br/>Left: <br/>Right: <br/>New: 1 2 3 4 7 8"]

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

《算法导论》中, 将左右数组的最后一项设为 $\infty$ , 只需要遍历到 $\infty$ 就意味着其中一个数组已经遍历完, 不需要像 MERGE-SORT 一样检查剩余元素. 这里用于简化边界条件的 $\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), 与之相对的就是递归条件(Recursive Case). 如 MERGE-SORT 的基本情况. ↩
这意味着右数组有 $⌈ n ⌉$ 个元素, 左数组有 $⌊ n ⌋$ 个元素. 其中 $⌈ x ⌉$ 表示大于或等于 $x$ 的最小整数, $⌊ x ⌋$ 表示小于或等于 $x$ 的最大整数. ↩
这只是辅助函数的时间复杂度, 归并排序的实际复杂度在后面解答. ↩

Keyboard shortcuts

算法学习