第21章 线性时间排序

学习目标

• 理解非比较排序突破 $O(n \log n)$ 下界的原理
• 掌握计数排序的正确性证明与复杂度分析
• 理解基数排序的LSD与MSD策略
• 掌握桶排序的概率分析
• 理解线性排序的适用条件与局限性

---

21.1 非比较排序理论

21.1.1 突破下界的条件

定理 21.1（比较排序下界） 任何比较排序算法的最坏情况时间复杂度为 $\Omega(n \log n)$。

问题：能否突破此下界？

定理 21.2（非比较排序突破） 若利用元素的特定性质（如整数值范围），可突破比较排序下界，达到 $O(n)$。

证明：比较排序下界基于决策树模型，假设仅能通过比较获取信息。若能直接访问元素的值（如作为数组下标），则可绕过决策树限制。 ∎

21.1.2 适用条件

定义 21.1（线性排序条件） 线性排序算法需满足：

1. 元素可映射到有限范围
2. 映射操作为 $O(1)$
3. 范围大小 $k$ 与 $n$ 相关

定理 21.3 若 $k = O(n)$，则计数排序为 $O(n)$。

---

21.2 计数排序

21.2.1 算法描述

定义 21.2（计数排序） 计数排序通过统计每个值的出现次数，然后按顺序输出。

算法 21.1（计数排序）

Counting-Sort(A, B, k):
    // A[1..n] 为输入，B[1..n] 为输出，元素范围 [0..k]
    let C[0..k] be new array
    for i = 0 to k:
        C[i] = 0
    for j = 1 to n:
        C[A[j]] = C[A[j]] + 1
    // C[i] 现在包含等于 i 的元素个数
    for i = 1 to k:
        C[i] = C[i] + C[i-1]
    // C[i] 现在包含小于等于 i 的元素个数
    for j = n downto 1:
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

21.2.2 正确性证明

定理 21.4（计数排序正确性） 计数排序正确排序数组，且是稳定排序。

证明：

1. 正确性：经过前缀和计算，$C[i]$ 表示小于等于 $i$ 的元素个数。当放置元素 $A[j]$ 时，$C[A[j]]$ 给出其在输出数组中的正确位置（从1开始计数）。

2. 稳定性：从后向前遍历输入数组，相等元素的相对顺序保持不变。设 $A[j_1] = A[j_2] = v$ 且 $j_1 < j_2$。由于从后向前处理，$A[j_2]$ 先被放置在位置 $C[v]$，然后 $C[v]$ 减1，$A[j_1]$ 被放置在位置 $C[v]-1$。因此 $A[j_1]$ 在 $A[j_2]$ 之前。 ∎

21.2.3 复杂度分析

定理 21.5 计数排序的时间复杂度为 $\Theta(n + k)$，空间复杂度为 $\Theta(n + k)$。

证明：

• 初始化 $C$：$k+1$ 次
• 统计计数：$n$ 次
• 计算前缀和：$k$ 次
• 放置元素：$n$ 次

总计 $\Theta(n + k)$。需要额外数组 $B$ 和 $C$，空间 $\Theta(n + k)$。 ∎

21.2.4 Python实现

from typing import List, TypeVar, Callable, Optional

T = TypeVar('T')

def counting_sort(arr: List[int], min_val: Optional[int] = None, max_val: Optional[int] = None) -> List[int]:
    if not arr:
        return []
    
    if min_val is None:
        min_val = min(arr)
    if max_val is None:
        max_val = max(arr)
    
    range_size = max_val - min_val + 1
    count = [0] * range_size
    
    for num in arr:
        count[num - min_val] += 1
    
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    result = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        num = arr[i]
        count[num - min_val] -= 1
        result[count[num - min_val]] = num
    
    return result

def counting_sort_generic(arr: List[T], key: Callable[[T], int], min_val: Optional[int] = None, max_val: Optional[int] = None) -> List[T]:
    if not arr:
        return []
    
    keys = [key(x) for x in arr]
    
    if min_val is None:
        min_val = min(keys)
    if max_val is None:
        max_val = max(keys)
    
    range_size = max_val - min_val + 1
    count = [0] * range_size
    
    for k in keys:
        count[k - min_val] += 1
    
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    result: List[T] = [None] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        k = keys[i]
        count[k - min_val] -= 1
        result[count[k - min_val]] = arr[i]
    
    return result

class CountingSort:
    def __init__(self, min_val: Optional[int] = None, max_val: Optional[int] = None):
        self.min_val = min_val
        self.max_val = max_val
    
    def sort(self, arr: List[int]) -> List[int]:
        return counting_sort(arr, self.min_val, self.max_val)
    
    def sort_generic(self, arr: List[T], key: Callable[[T], int]) -> List[T]:
        return counting_sort_generic(arr, key, self.min_val, self.max_val)

---

21.3 基数排序

21.3.1 算法描述

定义 21.3（基数排序） 基数排序按位排序，从最低位到最高位（LSD）或从最高位到最低位（MSD）。

算法 21.2（LSD基数排序）

Radix-Sort(A, d):
    for i = 1 to d:
        use a stable sort to sort array A on digit i

21.3.2 正确性证明

定理 21.6（LSD基数排序正确性） LSD基数排序正确排序 $d$ 位整数。

证明：对位数 $i$ 归纳。

基础：$i=1$，按最低位排序，正确。

归纳：设前 $i-1$ 位已正确排序。第 $i$ 位排序时：

• 若两数第 $i$ 位不同，排序后顺序正确
• 若两数第 $i$ 位相同，稳定排序保持前 $i-1$ 位确定的顺序

因此，$d$ 位后完全排序。 ∎

定理 21.7（LSD与MSD比较）

• LSD：从低位到高位，必须使用稳定排序
• MSD：从高位到低位，可递归处理子问题

21.3.3 复杂度分析

定理 21.8 设 $n$ 个 $d$ 位整数，每位取值范围 $k$，基数排序时间复杂度为 $O(d(n + k))$。

证明：每位使用计数排序，代价 $O(n + k)$。共 $d$ 位，总计 $O(d(n + k))$。 ∎

定理 21.9 对于 $b$ 位二进制整数，基数排序复杂度为 $O(\frac{b}{r}(n + 2^r))$，其中 $r$ 为每趟处理的位数。

最优选择：取 $r = \lfloor \log_2 n \rfloor$，复杂度为 $O(\frac{bn}{\log n})$。

21.3.4 Python实现

from typing import List, Callable, Optional

def radix_sort_lsd(arr: List[int], base: int = 10) -> List[int]:
    if not arr:
        return []
    
    result = arr.copy()
    max_val = max(abs(x) for x in result)
    
    has_negative = any(x < 0 for x in result)
    
    if has_negative:
        negatives = [-x for x in result if x < 0]
        positives = [x for x in result if x >= 0]
        
        sorted_negatives = radix_sort_lsd(negatives, base) if negatives else []
        sorted_positives = radix_sort_lsd(positives, base) if positives else []
        
        return [-x for x in reversed(sorted_negatives)] + sorted_positives
    
    exp = 1
    while max_val // exp > 0:
        result = _counting_sort_by_digit(result, exp, base)
        exp *= base
    
    return result

def _counting_sort_by_digit(arr: List[int], exp: int, base: int) -> List[int]:
    n = len(arr)
    result = [0] * n
    count = [0] * base
    
    for num in arr:
        digit = (num // exp) % base
        count[digit] += 1
    
    for i in range(1, base):
        count[i] += count[i - 1]
    
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % base
        count[digit] -= 1
        result[count[digit]] = arr[i]
    
    return result

def radix_sort_msd(arr: List[int], base: int = 10) -> List[int]:
    if not arr:
        return []
    
    max_val = max(abs(x) for x in arr) if arr else 0
    max_digits = 0
    temp = max_val
    while temp > 0:
        max_digits += 1
        temp //= base
    
    if max_digits == 0:
        return arr.copy()
    
    return _msd_sort(arr, max_digits - 1, base)

def _msd_sort(arr: List[int], digit_pos: int, base: int) -> List[int]:
    if len(arr) <= 1 or digit_pos < 0:
        return arr.copy()
    
    buckets: List[List[int]] = [[] for _ in range(base)]
    
    exp = base ** digit_pos
    for num in arr:
        digit = (num // exp) % base
        buckets[digit].append(num)
    
    result = []
    for bucket in buckets:
        if bucket:
            sorted_bucket = _msd_sort(bucket, digit_pos - 1, base)
            result.extend(sorted_bucket)
    
    return result

def radix_sort_strings(arr: List[str]) -> List[str]:
    if not arr:
        return []
    
    max_len = max(len(s) for s in arr)
    
    padded = [(s.ljust(max_len, '\0'), i) for i, s in enumerate(arr)]
    
    for pos in range(max_len - 1, -1, -1):
        padded = _counting_sort_by_char(padded, pos)
    
    return [arr[i] for _, i in padded]

def _counting_sort_by_char(arr: List[tuple], pos: int) -> List[tuple]:
    n = len(arr)
    result = [None] * n
    count = [0] * 256
    
    for s, _ in arr:
        count[ord(s[pos])] += 1
    
    for i in range(1, 256):
        count[i] += count[i - 1]
    
    for i in range(n - 1, -1, -1):
        s, idx = arr[i]
        char_idx = ord(s[pos])
        count[char_idx] -= 1
        result[count[char_idx]] = (s, idx)
    
    return result

class RadixSort:
    def __init__(self, base: int = 10):
        self.base = base
    
    def sort(self, arr: List[int]) -> List[int]:
        return radix_sort_lsd(arr, self.base)
    
    def sort_strings(self, arr: List[str]) -> List[str]:
        return radix_sort_strings(arr)

---

21.4 桶排序

21.4.1 算法描述

定义 21.4（桶排序） 桶排序将元素分配到若干桶中，每个桶单独排序后合并。

算法 21.3（桶排序）

Bucket-Sort(A):
    n = len(A)
    create n empty buckets B[0..n-1]
    for i = 0 to n-1:
        insert A[i] into bucket B[n * A[i]]
    for i = 0 to n-1:
        sort bucket B[i] with insertion sort
    concatenate the lists B[0], B[1], ..., B[n-1]

21.4.2 概率分析

假设 21.1（均匀分布假设） 输入元素独立均匀分布在 $[0, 1)$ 区间。

定理 21.10（桶大小期望） 在均匀分布假设下，每个桶期望包含 $O(1)$ 个元素。

证明：元素落入桶 $i$ 的概率为 $\frac{1}{n}$。设 $n_i$ 为桶 $i$ 的元素数：

$$E[n_i] = n \cdot \frac{1}{n} = 1$$

由泊松分布近似，$P(n_i = k) \approx \frac{e^{-1}}{k!}$。 ∎

定理 21.11（桶排序期望复杂度） 在均匀分布假设下，桶排序期望时间为 $\Theta(n)$。

证明：设 $n_i$ 为桶 $i$ 的元素数。插入排序时间为 $O(n_i^2)$。

$$E[T] = \Theta(n) + \sum_{i=0}^{n-1} E[O(n_i^2)] = \Theta(n) + n \cdot E[O(n_0^2)]$$

由泊松分布，$E[n_0^2] = \text{Var}(n_0) + E[n_0]^2 = 1 + 1 = 2$。

故 $E[T] = \Theta(n) + n \cdot O(1) = \Theta(n)$。 ∎

21.4.3 Python实现

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

T = TypeVar('T')

def bucket_sort(arr: List[float], num_buckets: Optional[int] = None) -> List[float]:
    if not arr:
        return []
    
    n = len(arr)
    if num_buckets is None:
        num_buckets = n
    
    buckets: List[List[float]] = [[] for _ in range(num_buckets)]
    
    for num in arr:
        bucket_idx = min(int(num * num_buckets), num_buckets - 1)
        buckets[bucket_idx].append(num)
    
    for bucket in buckets:
        bucket.sort()
    
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

def bucket_sort_generic(arr: List[T], key: Callable[[T], float], num_buckets: Optional[int] = None) -> List[T]:
    if not arr:
        return []
    
    n = len(arr)
    if num_buckets is None:
        num_buckets = n
    
    min_key = min(key(x) for x in arr)
    max_key = max(key(x) for x in arr)
    
    if min_key == max_key:
        return arr.copy()
    
    buckets: List[List[T]] = [[] for _ in range(num_buckets)]
    
    for item in arr:
        k = key(item)
        normalized = (k - min_key) / (max_key - min_key)
        bucket_idx = min(int(normalized * num_buckets), num_buckets - 1)
        buckets[bucket_idx].append(item)
    
    for bucket in buckets:
        bucket.sort(key=key)
    
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

def bucket_sort_integers(arr: List[int], min_val: Optional[int] = None, max_val: Optional[int] = None) -> List[int]:
    if not arr:
        return []
    
    if min_val is None:
        min_val = min(arr)
    if max_val is None:
        max_val = max(arr)
    
    if min_val == max_val:
        return arr.copy()
    
    n = len(arr)
    num_buckets = min(n, max_val - min_val + 1)
    
    buckets: List[List[int]] = [[] for _ in range(num_buckets)]
    
    range_size = max_val - min_val + 1
    bucket_size = math.ceil(range_size / num_buckets)
    
    for num in arr:
        bucket_idx = (num - min_val) // bucket_size
        bucket_idx = min(bucket_idx, num_buckets - 1)
        buckets[bucket_idx].append(num)
    
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    
    return result

class BucketSort:
    def __init__(self, num_buckets: Optional[int] = None):
        self.num_buckets = num_buckets
    
    def sort(self, arr: List[float]) -> List[float]:
        return bucket_sort(arr, self.num_buckets)
    
    def sort_generic(self, arr: List[T], key: Callable[[T], float]) -> List[T]:
        return bucket_sort_generic(arr, key, self.num_buckets)
    
    def sort_integers(self, arr: List[int], min_val: Optional[int] = None, max_val: Optional[int] = None) -> List[int]:
        return bucket_sort_integers(arr, min_val, max_val)

---

21.5 算法比较与应用

21.5.1 复杂度对比

算法	时间复杂度	空间复杂度	稳定性	适用条件
计数排序	$\Theta(n + k)$	$\Theta(n + k)$	稳定	整数，范围有限
基数排序	$\Theta(d(n + k))$	$\Theta(n + k)$	稳定	可分解为位
桶排序	$\Theta(n)$ 期望	$\Theta(n)$	稳定	均匀分布

21.5.2 选择策略

定理 21.12（算法选择准则）

1. 计数排序：当 $k = O(n)$ 时最优
2. 基数排序：当 $d$ 为常数且 $k = O(n)$ 时最优
3. 桶排序：当输入均匀分布时最优

21.5.3 实际应用

应用场景	推荐算法	原因
年龄排序	计数排序	范围有限（0-150）
字符串排序	基数排序	可按字符分解
浮点数排序	桶排序	均匀分布假设
大整数排序	基数排序	按位处理

---

21.6 理论极限

21.6.1 排序问题的信息论视角

定理 21.13 排序问题的信息论下界为 $\log_2(n!) = \Theta(n \log n)$ 比特。

定理 21.14 非比较排序通过直接访问元素值，获取更多信息，从而突破下界。

21.6.2 字典序排序下界

定理 21.15（字典序排序下界） 在比较模型下，字典序排序的下界为 $\Omega(n \log n)$。

证明：字典序排列数仍为 $n!$，决策树论证同样适用。 ∎

---

21.7 本章小结

本章介绍了线性时间排序算法：

1. 理论突破：利用元素性质突破比较排序下界
2. 计数排序：统计频次，$O(n + k)$，适用于有限范围整数
3. 基数排序：按位排序，$O(d(n + k))$，适用于可分解元素
4. 桶排序：分桶处理，$O(n)$ 期望，适用于均匀分布
5. 适用条件：线性排序需满足特定假设

---

参考文献

1. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
2. Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.
3. Radix sort. (2021). In Wikipedia.
4. Counting sort. (2021). In Wikipedia.
5. Bucket sort. (2021). In Wikipedia.

---

下一章：第22章 搜索算法