全排列排序#

数组 $A$ 共有 $n!$ 种排列，其中至少有一种排列是有序的。

对每种排列，在 $\Theta(n)$ 时间内检查其是否已排序。

示例： $[2, 3, 1] \to \{[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]\}$

1
def permutation_sort(A):
2
    """对 A 进行排序"""
3
    for B in permutations(A):     # O(n!) 次循环
4
        if is_sorted(B):           # O(n)
5
            return B               # O(1)

分析：

• 正确性： 通过穷举所有可能性进行个案分析（暴力解）。
• 运行时间： $\Omega(n! \cdot n)$，这是指数级/阶乘级的，极其低效 :(

选择排序#

在前缀 $A[:i + 1]$ 中找出最大数，并将其与 $A[i]$ 交换位置。

递归地对前缀 $A[:i]$ 进行排序。

示例： $[8, 2, 4, 9, 3] \to [8, 2, 4, 3, 9] \to [3, 2, 4, 8, 9] \to [3, 2, 4, 8, 9] \to [2, 3, 4, 8, 9]$

1
def selection_sort(A, i=None):         # T(i)
2
    """排序 A[:i + 1]"""
3
    if i is None:
4
        i = len(A) - 1                 # O(1)
5
    if i > 0:                          # O(1)
6
        j = prefix_max(A, i)           # S(i)
7
        A[i], A[j] = A[j], A[i]        # O(1)
8
        selection_sort(A, i - 1)       # T(i - 1)
9

10
def prefix_max(A, i):                  # S(i)
11
    """返回 A[:i + 1] 中最大元素的索引"""
12
    if i > 0:                          # O(1)
13
        j = prefix_max(A, i - 1)       # S(i - 1)
14
        if A[i] < A[j]:                # O(1)
15
            return j                   # O(1)
16
    return i                           # O(1)

展开收起

prefix_max​ 分析：

基本情况： 当 $i = 0$ 时，数组只有 1 个元素，最大值的索引就是 $i$。

归纳假设： 假设对 $i-1$ 成立，则当前最大值要么是 $A[:i]$ 中的最大值，要么是 $A[i]$，算法在两种情况下均能返回正确索引。

递推关系： $S(1) = \Theta(1), \quad S(n) = S(n - 1) + \Theta(1)$

• 代入法： 猜 $S(n) = \Theta(n)$，验证 $cn = \Theta(1) + c(n - 1) \implies c = \Theta(1)$ 成立。

• 递归树： 深度为 $n$ 的链，每个节点做 $\Theta(1)$ 的工作，$\sum_{i=0}^{n-1} 1 = \Theta(n)$。

  1
  S(n)
  2
  = S(n-1) + Θ(1)
  3
  = S(n-2) + Θ(1) + Θ(1)
  4
  = S(n-3) + Θ(1) + Θ(1) + Θ(1)
  5
  ...
  6
  = Θ(1) + n 个左右的 Θ(1)
  7
  = Θ(n)

selection_sort​ 分析：

基本情况： 当 $i = 0$ 时，数组只有 1 个元素，天然有序。

归纳假设： 假设selection_sort(A, i-1)​ 能正确排序 A[:i]​，证明 selection_sort(A,i)​ 能正确排序 A[:i+1]。

递推关系： $T(1) = \Theta(1), \quad T(n) = T(n - 1) + \Theta(n)$

• 代入法： 猜 $T(n) = \Theta(n^2)$，验证 $cn^2 = \Theta(n) + c(n - 1)^2 \implies c(2n - 1) = \Theta(n)$ 成立。
• 递归树： 深度为 $n$ 的链，第 $i$ 个节点做 $\Theta(i)$ 的工作，$\sum_{i=0}^{n-1} i = \Theta(n^2)$。

插入排序#

递归地对前缀 $A[:i]$ 进行排序。

在假定前缀 $A[:i]$ 已排序的前提下，通过连续交换将新元素插入到合适位置，使得前缀 $A[:i + 1]$ 保持有序。

示例： $[8, 2, 4, 9, 3] \to [2, 8, 4, 9, 3] \to [2, 4, 8, 9, 3] \to [2, 4, 8, 9, 3] \to [2, 3, 4, 8, 9]$

1
def insertion_sort(A, i=None):         # T(i)
2
    """排序 A[:i + 1]"""
3
    if i is None:
4
        i = len(A) - 1                 # O(1)
5
    if i > 0:                          # O(1)
6
        insertion_sort(A, i - 1)       # T(i - 1)
7
        insert_last(A, i)              # S(i)
8

9
def insert_last(A, i):                 # S(i)
10
    """在假定 A[:i] 已排序的前提下，排序 A[:i + 1]"""
11
    if i > 0 and A[i] < A[i - 1]:      # O(1)
12
        A[i], A[i - 1] = A[i - 1], A[i]# O(1)
13
        insert_last(A, i - 1)          # S(i - 1)

insert_last​ 分析：

基本情况： 当 $i = 0$ 时，数组只有 1 个元素，已有序。

归纳假设： 假设对 $i$ 成立。若 $A[i] \ge A[i - 1]$，则整体已有序；否则，交换最后两个元素后，由归纳假设可以继续正确排序 $A[:i]$。

递推关系： $S(1) = \Theta(1), \quad S(n) = S(n - 1) + \Theta(1) \implies S(n) = \Theta(n)$。

insertion_sort​ 分析：

基本情况： 当 $i = 0$ 时，数组只有 1 个元素，已有序。

归纳假设： 假设对 $i$ 成立。算法先递归地将 $A[:i]$ 排好序，再利用前面证明的 insert_last 正确处理剩余部分。

递推关系： $T(1) = \Theta(1), \quad T(n) = T(n - 1) + \Theta(n) \implies T(n) = \Theta(n^2)$。

归并排序#

递归地对前半部分和后半部分分别进行排序（可先假设元素个数为 2 的幂）。

将两个已排序的半区合并为一个有序列表（双指针/双指法算法，two finger algorithm）。

示例： $[7, 1, 5, 6, 2, 4, 9, 3] \to [1, 7, 5, 6, 2, 4, 3, 9] \to [1, 5, 6, 7, 2, 3, 4, 9] \to [1, 2, 3, 4, 5, 6, 7, 9]$

1
def merge_sort(A, a=0, b=None):        # T(b - a = n)
2
    """排序 A[a:b]"""
3
    if b is None:
4
        b = len(A)                     # O(1)
5
    if 1 < b - a:                      # O(1)
6
        c = (a + b + 1) // 2           # O(1)
7
        merge_sort(A, a, c)            # T(n / 2)
8
        merge_sort(A, c, b)            # T(n / 2)
9
        L, R = A[a:c], A[c:b]          # O(n)
10
        merge(L, R, A, len(L), len(R), a, b) # S(n)
11

12
def merge(L, R, A, i, j, a, b):        # S(b - a = n)
13
    """将已排序的 L[:i] 和 R[:j] 合并放入 A[a:b]"""
14
    if a < b:                          # O(1)
15
        if (j <= 0) or (i > 0 and L[i - 1] > R[j - 1]): # O(1)
16
            A[b - 1] = L[i - 1]        # O(1)
17
            i = i - 1                  # O(1)
18
        else:                          # O(1)
19
            A[b - 1] = R[j - 1]        # O(1)
20
            j = j - 1                  # O(1)
21
        merge(L, R, A, i, j, a, b - 1) # S(n - 1)

展开收起

merge​ 分析：

基本情况： 当 $n = 0$ 时，数组均为空，结论平凡成立（vacuously correct）。

归纳假设： 假设对规模 $n$ 成立。填入 $A[b-1]$ 的元素必须是 $L$ 和 $R$ 剩余未合并前缀中的最大值；由于 $L$ 和 $R$ 各自有序，只需比较二者末尾元素取较大者即可；剩下的元素通过归纳假设递归合并完成。 $\square$

递推关系： $S(0) = \Theta(1), \quad S(n) = S(n - 1) + \Theta(1) \implies S(n) = \Theta(n)$。

merge_sort​ 分析：

基本情况： 当 $n = 1$ 时，数组只有 1 个元素，已有序。

归纳假设： 假设对所有 $k < n$ 均成立。算法通过归纳假设正确排好两个较小的半区，然后经由上述 merge 函数合并为有序数组。 $\square$

递推关系： $T(1) = \Theta(1), \quad T(n) = 2T(n/2) + \Theta(n)$

• 代入法： 猜测 $T(n) = \Theta(n \log n)$
  ​$cn \log n = \Theta(n) + 2c(n/2)\log(n/2) \implies cn \log(2) = \Theta(n)$ 成立。

• 递归树： 深度为 $\log_2 n$ 且有 $n$ 个叶节点的完全二叉树。第 $i$ 层有 $2^i$ 个节点，每个节点耗费 $O(n/2^i)$ 的工作量。
  总工作量为：

  $$\sum_{i=0}^{\log_2 n} (2^i) \cdot \left(\frac{n}{2^i}\right) = \sum_{i=0}^{\log_2 n} n = \Theta(n \log n)$$

‍