第19章 排序算法理论

学习目标

• 掌握排序问题的形式化定义与分类
• 理解比较排序的下界证明
• 掌握基本排序算法的正确性证明与复杂度分析
• 理解排序算法的稳定性与适用场景
• 掌握排序算法的选择策略

---

19.1 排序问题的形式化定义

19.1.1 问题定义

定义 19.1（排序问题） 给定 $n$ 个元素的序列 $\langle a_1, a_2, \ldots, a_n \rangle$，求一个排列 $\langle a'_1, a'_2, \ldots, a'_n \rangle$，满足 $a'_1 \leq a'_2 \leq \ldots \leq a'_n$。

定义 19.2（全序关系） 集合 $S$ 上的关系 $\leq$ 称为全序，若满足：

1. 自反性：$\forall a \in S: a \leq a$
2. 反对称性：$\forall a, b \in S: a \leq b \land b \leq a \Rightarrow a = b$
3. 传递性：$\forall a, b, c \in S: a \leq b \land b \leq c \Rightarrow a \leq c$
4. 完全性：$\forall a, b \in S: a \leq b \lor b \leq a$

定义 19.3（稳定排序） 若排序算法保持相等元素的相对顺序，则称其为稳定的。即若 $a_i = a_j$ 且 $i < j$，则排序后 $a_i$ 仍在 $a_j$ 之前。

19.1.2 排序算法分类

定义 19.4（比较排序） 仅通过比较元素对来确定相对顺序的排序算法。

定义 19.5（非比较排序） 利用元素的特定性质（如整数范围）进行排序的算法。

---

19.2 比较排序的下界

19.2.1 决策树模型

定义 19.6（决策树） 比较排序的决策树是一棵二叉树：

• 每个内部节点表示一次比较 $a_i : a_j$
• 左子树对应 $a_i \leq a_j$，右子树对应 $a_i > a_j$
• 每个叶节点表示一种排列

定理 19.1（决策树高度） 对 $n$ 个元素排序的决策树高度 $h$ 满足：

$$h \geq \log_2(n!) = \Omega(n \log n)$$

证明：决策树必须有 $n!$ 个叶节点（对应所有排列）。高度为 $h$ 的二叉树最多有 $2^h$ 个叶节点，故：

$$2^h \geq n! \Rightarrow h \geq \log_2(n!)$$

由Stirling公式：

$$\log_2(n!) = \sum_{i=1}^{n} \log_2 i \geq \int_1^n \log_2 x , dx = n \log_2 n - \frac{n}{\ln 2} + O(1) = \Omega(n \log n)$$

∎

推论 19.1 任何比较排序算法的最坏情况时间复杂度为 $\Omega(n \log n)$。

19.2.2 信息论下界

定理 19.2（信息论下界） 排序问题的信息论下界为 $\log_2(n!)$ 次比较。

证明：排序问题的输出空间大小为 $n!$（所有排列）。每次比较最多将输出空间减半。需要至少 $\log_2(n!)$ 次比较才能确定唯一输出。 ∎

---

19.3 冒泡排序

19.3.1 算法描述

算法 19.1（冒泡排序）

Bubble-Sort(A):
    for i = 1 to n-1:
        for j = n downto i+1:
            if A[j] < A[j-1]:
                exchange A[j] with A[j-1]

19.3.2 正确性证明

定理 19.3（冒泡排序正确性） 冒泡排序终止时，数组按非递减顺序排列。

证明：使用循环不变式：在第 $i$ 轮外循环后，$A[1..i]$ 包含原数组中最小的 $i$ 个元素，且已排序。

初始化：$i = 0$，空集，成立。

保持：第 $i$ 轮内循环将 $A[i+1..n]$ 中的最小元素"冒泡"到位置 $i+1$。因为每次比较相邻元素并交换，最终 $A[i+1]$ 是 $A[i+1..n]$ 中的最小值。由归纳假设，$A[1..i]$ 已排序且包含最小的 $i$ 个元素，故 $A[1..i+1]$ 包含最小的 $i+1$ 个元素且已排序。

终止：$i = n-1$，$A[1..n-1]$ 已排序且包含最小的 $n-1$ 个元素，故 $A[n]$ 是最大元素，整个数组已排序。 ∎

19.3.3 复杂度分析

定理 19.4 冒泡排序的时间复杂度为：

• 最坏情况：$O(n^2)$
• 最好情况：$O(n)$（已排序数组，带优化）
• 平均情况：$O(n^2)$

证明：

• 最坏情况：外循环 $n-1$ 次，第 $i$ 次内循环 $n-i$ 次，总比较次数：

$$\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = O(n^2)$$

• 最好情况：若已排序，第一轮无交换，提前终止，$O(n)$。
• 平均情况：逆序对期望为 $\frac{n(n-1)}{4}$，每次交换消除一个逆序对，故 $O(n^2)$。 ∎

19.3.4 Python实现

from typing import List, TypeVar, Callable, Optional

T = TypeVar('T')

def bubble_sort(arr: List[T], key: Optional[Callable[[T], any]] = None, reverse: bool = False) -> List[T]:
    n = len(arr)
    result = arr.copy()
    
    def compare(a: T, b: T) -> bool:
        ka = key(a) if key else a
        kb = key(b) if key else b
        return ka > kb if not reverse else ka < kb
    
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if compare(result[j], result[j + 1]):
                result[j], result[j + 1] = result[j + 1], result[j]
                swapped = True
        if not swapped:
            break
    
    return result

def bubble_sort_inplace(arr: List[T]) -> None:
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

---

19.4 选择排序

19.4.1 算法描述

算法 19.2（选择排序）

Selection-Sort(A):
    for i = 1 to n-1:
        min_idx = i
        for j = i+1 to n:
            if A[j] < A[min_idx]:
                min_idx = j
        exchange A[i] with A[min_idx]

19.4.2 正确性证明

定理 19.5（选择排序正确性） 选择排序终止时，数组已排序。

证明：循环不变式：在第 $i$ 轮后，$A[1..i]$ 包含原数组中最小的 $i$ 个元素，且已排序。

第 $i$ 轮在 $A[i..n]$ 中找到最小元素，与 $A[i]$ 交换。由归纳假设，$A[1..i-1]$ 已包含最小的 $i-1$ 个元素，故 $A[1..i]$ 包含最小的 $i$ 个元素。 ∎

19.4.3 复杂度分析

定理 19.6 选择排序的时间复杂度为 $\Theta(n^2)$，无论输入如何。

证明：比较次数：

$$\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}$$

交换次数：$n-1$ 次。总复杂度 $\Theta(n^2)$。 ∎

19.4.4 Python实现

def selection_sort(arr: List[T], key: Optional[Callable[[T], any]] = None, reverse: bool = False) -> List[T]:
    n = len(arr)
    result = arr.copy()
    
    def get_key(x: T) -> any:
        return key(x) if key else x
    
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            kj, kmin = get_key(result[j]), get_key(result[min_idx])
            if (kj < kmin) != reverse:
                min_idx = j
        if min_idx != i:
            result[i], result[min_idx] = result[min_idx], result[i]
    
    return result

---

19.5 插入排序

19.5.1 算法描述

算法 19.3（插入排序）

Insertion-Sort(A):
    for j = 2 to n:
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key:
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

19.5.2 正确性证明

定理 19.7（插入排序正确性） 插入排序终止时，数组已排序。

证明：循环不变式：在外循环第 $j$ 次迭代开始时，$A[1..j-1]$ 包含原 $A[1..j-1]$ 中的元素，且已排序。

初始化：$j=2$，$A[1]$ 单元素，已排序。

保持：将 $A[j]$ 插入正确位置，移动 $A[1..j-1]$ 中大于 $A[j]$ 的元素向右一位，保持 $A[1..j]$ 已排序。

终止：$j=n+1$，$A[1..n]$ 已排序。 ∎

19.5.3 复杂度分析

定理 19.8 插入排序的时间复杂度为：

• 最坏情况：$\Theta(n^2)$（逆序数组）
• 最好情况：$\Theta(n)$（已排序数组）
• 平均情况：$\Theta(n^2)$

证明：设 $I$ 为逆序对数。每次内循环迭代消除一个逆序对。总比较次数为 $n-1+I$。

• 最坏情况：$I = \frac{n(n-1)}{2}$，$\Theta(n^2)$
• 最好情况：$I = 0$，$\Theta(n)$
• 平均情况：$E[I] = \frac{n(n-1)}{4}$，$\Theta(n^2)$

∎

19.5.4 Python实现

def insertion_sort(arr: List[T], key: Optional[Callable[[T], any]] = None, reverse: bool = False) -> List[T]:
    n = len(arr)
    result = arr.copy()
    
    def get_key(x: T) -> any:
        return key(x) if key else x
    
    for i in range(1, n):
        current = result[i]
        j = i - 1
        
        while j >= 0:
            kj, kcurrent = get_key(result[j]), get_key(current)
            should_move = (kj > kcurrent) if not reverse else (kj < kcurrent)
            if not should_move:
                break
            result[j + 1] = result[j]
            j -= 1
        
        result[j + 1] = current
    
    return result

def binary_insertion_sort(arr: List[T]) -> List[T]:
    result = arr.copy()
    n = len(result)
    
    def binary_search(val: T, left: int, right: int) -> int:
        while left < right:
            mid = (left + right) // 2
            if result[mid] <= val:
                left = mid + 1
            else:
                right = mid
        return left
    
    for i in range(1, n):
        current = result[i]
        pos = binary_search(current, 0, i)
        
        for j in range(i, pos, -1):
            result[j] = result[j - 1]
        result[pos] = current
    
    return result

---

19.6 希尔排序

19.6.1 算法描述

定义 19.7（间隔序列） 希尔排序使用递减的间隔序列 $h_1 > h_2 > \ldots > h_k = 1$，对每个间隔执行插入排序。

算法 19.4（希尔排序）

Shell-Sort(A):
    for each h in gap sequence:
        for i = h+1 to n:
            temp = A[i]
            j = i
            while j > h and A[j-h] > temp:
                A[j] = A[j-h]
                j = j - h
            A[j] = temp

19.6.2 复杂度分析

定理 19.9 希尔排序的复杂度取决于间隔序列：

• Shell序列 ${n/2, n/4, \ldots, 1}$：$O(n^2)$
• Hibbard序列 ${2^k-1}$：$O(n^{3/2})$
• Sedgewick序列：$O(n^{4/3})$

19.6.3 Python实现

def shell_sort(arr: List[T], gaps: Optional[List[int]] = None) -> List[T]:
    n = len(arr)
    result = arr.copy()
    
    if gaps is None:
        gaps = []
        h = 1
        while h < n:
            gaps.insert(0, h)
            h = 3 * h + 1
    
    for gap in gaps:
        for i in range(gap, n):
            temp = result[i]
            j = i
            while j >= gap and result[j - gap] > temp:
                result[j] = result[j - gap]
                j -= gap
            result[j] = temp
    
    return result

---

19.7 快速排序

19.7.1 算法描述

算法 19.5（快速排序）

Quick-Sort(A, p, r):
    if p < r:
        q = Partition(A, p, r)
        Quick-Sort(A, p, q-1)
        Quick-Sort(A, q+1, r)

Partition(A, p, r):
    x = A[r]
    i = p - 1
    for j = p to r-1:
        if A[j] <= x:
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1

19.7.2 正确性证明

定理 19.10（Partition正确性） Partition返回下标 $q$，满足：

• $A[p..q-1] \leq A[q]$
• $A[q+1..r] > A[q]$

证明：循环不变式：对于任意 $k$：

• 若 $p \leq k \leq i$，则 $A[k] \leq x$
• 若 $i+1 \leq k \leq j-1$，则 $A[k] > x$
• 若 $k = r$，则 $A[k] = x$

循环结束时 $j = r$，交换 $A[i+1]$ 与 $A[r]$，$A[i+1] = x$，满足条件。 ∎

19.7.3 复杂度分析

定理 19.11（快速排序最坏情况） 最坏情况下快速排序时间为 $\Theta(n^2)$。

证明：当每次划分产生 $0$ 和 $n-1$ 的子问题时：

$$T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$$

∎

定理 19.12（快速排序平均情况） 在随机输入下，快速排序期望时间为 $O(n \log n)$。

证明：设 $T(n)$ 为期望时间。随机选择主元时：

$$T(n) = \frac{1}{n}\sum_{q=1}^{n}(T(q-1) + T(n-q)) + \Theta(n)$$

可证明 $T(n) \leq 2n \ln n = O(n \log n)$。 ∎

定理 19.13（随机化快速排序） 随机选择主元可将期望时间保证为 $O(n \log n)$。

19.7.4 Python实现

import random
from typing import List, TypeVar, Callable, Optional

T = TypeVar('T')

def quick_sort(arr: List[T], key: Optional[Callable[[T], any]] = None, reverse: bool = False) -> List[T]:
    if len(arr) <= 1:
        return arr.copy()
    
    def get_key(x: T) -> any:
        return key(x) if key else x
    
    pivot = arr[len(arr) // 2]
    pivot_key = get_key(pivot)
    
    left = [x for x in arr if (get_key(x) < pivot_key) != reverse and get_key(x) != pivot_key]
    middle = [x for x in arr if get_key(x) == pivot_key]
    right = [x for x in arr if (get_key(x) > pivot_key) != reverse and get_key(x) != pivot_key]
    
    return quick_sort(left, key, reverse) + middle + quick_sort(right, key, reverse)

def quick_sort_inplace(arr: List[T], low: int = 0, high: Optional[int] = None) -> None:
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)

def partition(arr: List[T], low: int, high: int) -> int:
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort_randomized(arr: List[T]) -> List[T]:
    result = arr.copy()
    
    def _sort(low: int, high: int) -> None:
        if low < high:
            rand_idx = random.randint(low, high)
            result[rand_idx], result[high] = result[high], result[rand_idx]
            
            pivot_idx = partition(result, low, high)
            _sort(low, pivot_idx - 1)
            _sort(pivot_idx + 1, high)
    
    _sort(0, len(result) - 1)
    return result

def quick_sort_three_way(arr: List[T]) -> List[T]:
    if len(arr) <= 1:
        return arr.copy()
    
    pivot = arr[random.randint(0, len(arr) - 1)]
    
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    
    return quick_sort_three_way(less) + equal + quick_sort_three_way(greater)

---

19.8 归并排序

19.8.1 算法描述

算法 19.6（归并排序）

Merge-Sort(A, p, r):
    if p < r:
        q = floor((p + r) / 2)
        Merge-Sort(A, p, q)
        Merge-Sort(A, q+1, r)
        Merge(A, p, q, r)

Merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    create L[1..n1+1] and R[1..n2+1]
    for i = 1 to n1:
        L[i] = A[p+i-1]
    for j = 1 to n2:
        R[j] = A[q+j]
    L[n1+1] = ∞
    R[n2+1] = ∞
    i = 1, j = 1
    for k = p to r:
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

19.8.2 正确性证明

定理 19.14（归并排序正确性） 归并排序正确排序数组。

证明：对数组长度 $n$ 归纳。

• $n=1$：单元素已排序。
• 设对长度 $< n$ 的数组正确。长度为 $n$ 时，分为两半，由归纳假设各自正确排序。Merge操作正确合并两个已排序数组。 ∎

19.8.3 复杂度分析

定理 19.15 归并排序的时间复杂度为 $\Theta(n \log n)$。

证明：递推关系：

$$T(n) = 2T(n/2) + \Theta(n)$$

由主定理，$T(n) = \Theta(n \log n)$。 ∎

定理 19.16 归并排序的空间复杂度为 $\Theta(n)$。

19.8.4 Python实现

from typing import List, TypeVar, Callable, Optional

T = TypeVar('T')

def merge_sort(arr: List[T], key: Optional[Callable[[T], any]] = None, reverse: bool = False) -> List[T]:
    if len(arr) <= 1:
        return arr.copy()
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid], key, reverse)
    right = merge_sort(arr[mid:], key, reverse)
    
    return _merge(left, right, key, reverse)

def _merge(left: List[T], right: List[T], key: Optional[Callable[[T], any]], reverse: bool) -> List[T]:
    def get_key(x: T) -> any:
        return key(x) if key else x
    
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        kl, kr = get_key(left[i]), get_key(right[j])
        if (kl <= kr) != reverse:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort_inplace(arr: List[T]) -> None:
    n = len(arr)
    temp = [None] * n
    
    def _sort(left: int, right: int) -> None:
        if left >= right:
            return
        
        mid = (left + right) // 2
        _sort(left, mid)
        _sort(mid + 1, right)
        _merge_inplace(left, mid, right)
    
    def _merge_inplace(left: int, mid: int, right: int) -> None:
        for i in range(left, right + 1):
            temp[i] = arr[i]
        
        i, j, k = left, mid + 1, left
        
        while i <= mid and j <= right:
            if temp[i] <= temp[j]:
                arr[k] = temp[i]
                i += 1
            else:
                arr[k] = temp[j]
                j += 1
            k += 1
        
        while i <= mid:
            arr[k] = temp[i]
            i += 1
            k += 1
    
    _sort(0, n - 1)

def merge_sort_natural(arr: List[T]) -> List[T]:
    if len(arr) <= 1:
        return arr.copy()
    
    runs = []
    start = 0
    
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            runs.append(arr[start:i])
            start = i
    runs.append(arr[start:])
    
    while len(runs) > 1:
        new_runs = []
        for i in range(0, len(runs) - 1, 2):
            new_runs.append(_merge(runs[i], runs[i + 1], None, False))
        if len(runs) % 2 == 1:
            new_runs.append(runs[-1])
        runs = new_runs
    
    return runs[0] if runs else []

---

19.9 堆排序

19.9.1 算法描述

算法 19.7（堆排序）

Heap-Sort(A):
    Build-Max-Heap(A)
    for i = n downto 2:
        exchange A[1] with A[i]
        heap-size[A] = heap-size[A] - 1
        Max-Heapify(A, 1)

19.9.2 复杂度分析

定理 19.17 堆排序的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(1)$。

证明：

• Build-Max-Heap：$O(n)$
• $n-1$ 次Max-Heapify：每次 $O(\log n)$

总计 $O(n \log n)$。原地排序，空间 $O(1)$。 ∎

19.9.3 Python实现

def heap_sort(arr: List[T]) -> List[T]:
    result = arr.copy()
    n = len(result)
    
    def heapify(size: int, root: int) -> None:
        largest = root
        left = 2 * root + 1
        right = 2 * root + 2
        
        if left < size and result[left] > result[largest]:
            largest = left
        if right < size and result[right] > result[largest]:
            largest = right
        
        if largest != root:
            result[root], result[largest] = result[largest], result[root]
            heapify(size, largest)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    
    for i in range(n - 1, 0, -1):
        result[0], result[i] = result[i], result[0]
        heapify(i, 0)
    
    return result

---

19.10 算法比较

19.10.1 复杂度对比

算法	最好	平均	最坏	空间	稳定性
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n \log n)$	$O(n^{4/3})$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	不稳定
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳定
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定

19.10.2 选择策略

定理 19.18（排序算法选择）

1. 小规模数据（$n < 50$）：插入排序
2. 中等规模、内存受限：堆排序
3. 大规模、需稳定：归并排序
4. 大规模、平均性能优先：快速排序
5. 部分有序：插入排序或自适应排序

---

19.11 本章小结

本章系统介绍了比较排序算法：

1. 下界理论：比较排序的 $\Omega(n \log n)$ 下界
2. 简单排序：冒泡、选择、插入排序，$O(n^2)$
3. 高效排序：快速、归并、堆排序，$O(n \log n)$
4. 稳定性：相等元素相对顺序的保持
5. 选择策略：根据数据规模和特性选择算法

---

参考文献

1. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
2. Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1), 10-16.
3. Shell, D. L. (1959). A high-speed sorting procedure. Communications of the ACM, 2(7), 30-32.
4. Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347-348.
5. Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.

---

下一章：第20章 高级排序算法