3.5 线性时间排序

这一节，你能解决什么问题

学完这一节，你能够：

1. 判断什么时候可以用线性排序突破 Θ(n lg n) 下界，知道前提条件
2. 理解三种线性排序的原理：计数、基数、桶排序
3. 分析桶排序的期望复杂度，理解"均匀分布"的重要性
4. 审查 agent 的排序建议，发现前提条件错误

---

问题情境

回到上一节的故事：

工程师小李被告知"计数排序 O(n) 更快"，直接应用，系统崩溃。

为什么崩溃？

计数排序的前提：键值范围 k ≤ n 或 k = O(n)。

推荐系统的键是浮点数相关性得分，范围远超 n。

Cursor 不知道前提。小李没有验证。

问题：线性排序有什么前提条件？怎么判断是否满足？

---

直观思路

上一节证明了：比较排序有 Ω(n lg n) 下界。

但如果可以利用额外信息，就能突破。

三种突破思路：

1. 直接定位（计数排序）：不比较，直接数"有多少个这个值"
2. 逐位处理（基数排序）：把键分解成若干位，每位单独排序
3. 概率分布（桶排序）：利用均匀分布，期望每个桶只有少量元素

关键洞察：突破不是靠"更聪明的比较"，而是靠"利用额外信息"。

---

规范定义

计数排序

前提条件：键是整数，范围 k ≤ n 或 k = O(n)

原理：不比较，直接"计数定位"

算法思想：

1. 数每个值出现多少次
2. 把计数变成"第几个位置"
3. 按位置放入输出数组

基数排序

前提条件：键可以分解为 d 位，每位的范围有限

原理：从低位到高位，逐位稳定排序

算法思想：

1. 先按最低位排序
2. 再按次低位排序（稳定，保持低位顺序）
3. ...一直到最高位

桶排序

前提条件：输入均匀分布在 [0, 1)

原理：把区间分成 n 个桶，期望每个桶放 1 个元素

算法思想：

1. 把 [0, 1) 分成 n 个桶
2. 每个元素放入对应的桶
3. 每个桶内用插入排序
4. 串联所有桶

---

算法实现

计数排序

def counting_sort(A, k):
    # A 中元素范围 [0, k]
    C = [0] * (k + 1)       # 计数数组
    
    # 计数
    for x in A:
        C[x] += 1
    
    # 累计（变成"第几个位置"）
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    
    # 输出（从后往前，保证稳定）
    B = [0] * len(A)
    for i in range(len(A) - 1, -1, -1):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1
    
    return B

一步步执行：

输入：A = [2, 5, 3, 0, 2, 3, 0, 3]，k = 5

计数：C = [2, 0, 2, 3, 0, 1]
      （0出现2次，2出现2次，3出现3次，5出现1次）

累计：C = [2, 2, 4, 7, 7, 8]
      （值 ≤0 放前2位，值 ≤2 放前4位，...）

输出（从后往前，保证稳定）：
i=7: A[7]=3 → B[C[3]-1]=B[6]=3, C[3]=6
i=6: A[6]=0 → B[C[0]-1]=B[1]=0, C[0]=1
i=5: A[5]=3 → B[C[3]-1]=B[5]=3, C[3]=5
...

最终：B = [0, 0, 2, 2, 3, 3, 3, 5]

基数排序

def radix_sort(A, d):
    # d 是位数
    for i in range(d):
        # 用稳定排序按第 i 位排序（通常用计数排序）
        A = stable_sort_by_digit(A, i)
    return A

一步步执行：

输入：[329, 457, 657, 839, 436, 720, 355]

第1位（个位）排序：
  按个位：[720, 355, 436, 457, 657, 329, 839]
  
第2位（十位）排序（稳定）：
  按十位：[720, 355, 436, 457, 657, 329, 839]
  
第3位（百位）排序（稳定）：
  按百位：[329, 355, 436, 457, 657, 720, 839]

为什么必须稳定？

高位相同的元素，要保持低位已排好的顺序。

为什么从低位到高位？

低位先排好，高位排序时如果相同，稳定排序保持低位顺序。

桶排序

def bucket_sort(A):
    n = len(A)
    buckets = [[] for _ in range(n)]
    
    # 分桶
    for x in A:
        buckets[int(n * x)].append(x)
    
    # 每桶排序
    for bucket in buckets:
        insertion_sort(bucket)
    
    # 串联
    result = []
    for bucket in buckets:
        result.extend(bucket)
    return result

---

这个方法是怎么想到的

计数排序的思路

问题：比较排序有 Ω(n lg n) 下界，怎么突破？

洞察：如果知道键值范围有限，可以不比较，直接定位。

思路演化：

1. 朴素想法：每个可能的值，数有多少个。
2. 问题：怎么变成有序数组？
3. 解决：累计计数，变成"位置索引"。

基数排序的思路

问题：计数排序要求键值范围小。如果键值范围大怎么办？

洞察：把大键分解成若干小位。

思路演化：

1. 朴素想法：每位单独排序。
2. 问题：多位排序后怎么保持有序？
3. 解决：从低位到高位，每次用稳定排序。

桶排序的思路

问题：浮点数怎么线性排序？

洞察：如果分布均匀，期望每个桶只有少量元素。

思路演化：

1. 朴素想法：把区间分成若干桶。
2. 问题：桶内元素怎么排序？
3. 解决：桶内用插入排序，期望 Θ(1)。

---

正确性分析

计数排序：稳定性的关键

为什么从后往前输出？

因为累计计数是从前往后累计的。从后往前输出，保证相同值的元素保持原有顺序（稳定）。

证明：

设两个相同值 x 的元素，原位置 i < j。

从后往前处理时，j 先被放入，位置靠后。i 后被放入，位置靠前。

所以 i 的元素仍然在 j 的元素前面 → 稳定。

基数排序：稳定性的关键

为什么必须稳定？

假设两个元素在第 i 位相同，在第 i-1 位不同。

如果第 i 位排序不稳定，可能打乱第 i-1 位已排好的顺序。

证明：

从低位到高位排序。每次排序后，低位的顺序已正确。

高位排序时，如果高位相同，稳定排序保持低位顺序。

桶排序：期望分析

为什么期望 Θ(n)？

关键：每个桶期望放多少元素？

设均匀分布，P[元素落入桶 i] = 1/n。

设 n_i 是第 i 个桶的元素数。

E[n_i] = 1
E[n_i²] = 2 - 1/n

为什么 E[n_i²] = 2 - 1/n？

n_i = Σ_{j=1}^{n} I_j   （I_j 是指示器变量：元素 j 是否落入桶 i）

E[n_i²] = E[(Σ I_j)²]
        = Σ E[I_j²] + Σ_{j≠k} E[I_j × I_k]
        = n × 1/n + n(n-1) × 1/n²
        = 1 + (n-1)/n
        = 2 - 1/n

插入排序 Θ(n_i²)，所以：

E[总时间] = n × Θ(E[n_i²]) = n × Θ(2 - 1/n) = Θ(n)

---

复杂度分析

算法	时间	空间	稳定	适用条件
计数排序	Θ(n + k)	Θ(k)	✓	整数键，k ≤ n
基数排序	Θ(d(n + k))	Θ(n + k)	✓	可分解为 d 位
桶排序	Θ(n) 期望	Θ(n)	✓	均匀分布

关键问题：

• 计数排序：k >> n 时不可用
• 基数排序：d 很大时接近 Θ(n lg n)
• 桶排序：分布不均匀时退化

---

什么时候不该用这个方法

计数排序

该用：

• 键值范围小（k ≤ n）
• 键是整数
• 需要稳定

不该用：

• 键值范围大（k >> n）
• 键是浮点数或字符串
• 空间紧张（Θ(k) 额外空间）

基数排序

该用：

• 键可以分解（整数、字符串）
• 位数有限（d 不是太大）
• 需要稳定

不该用：

• 键不可分解（浮点数）
• 位数太大
• 空间紧张

桶排序

该用：

• 输入均匀分布
• 键是浮点数 [0, 1)
• 需要稳定

不该用：

• 输入分布不均匀
• 最坏保证要求（最坏 Θ(n²)）
• 键范围不在 [0, 1)

---

本节小结

解决了什么问题？

• Θ(n) 线性排序，突破 Ω(n lg n) 下界
• 前提条件不同，选择不同

核心方法是什么？

• 计数排序：直接定位，前提是键值范围小
• 基数排序：逐位处理，前提是键可分解
• 桶排序：利用分布，前提是均匀分布

为什么正确？

• 计数：累计计数 → 位置索引 → 直接定位
• 基数：低位到高位 + 稳定 → 保持低位顺序
• 桶：均匀分布 → 每桶期望 1 元素 → Θ(1) 排序

代价是什么？

• 计数：Θ(k) 额外空间
• 基数：Θ(n + k) 额外空间
• 桶：期望 Θ(n)，最坏 Θ(n²)

适用场景？

场景	推荐算法
年龄排序（0-150）	计数排序
电话号码排序	基数排序
随机成绩排序	桶排序
字符串字典序	基数排序
一般整数	快排/堆排序

---

练习

基本理解

练习 1：对数组 [1, 4, 1, 2, 7, 5, 2]，手动执行计数排序，画出每一步。

练习 2：对 [170, 45, 75, 90, 802, 24, 2, 66]，执行基数排序（按十进制位），画出每一步。

练习 3：为什么基数排序必须从低位到高位？给出一个反例说明从高位到低位会失败。

方法应用

练习 4：设计一个计数排序的变体，用于排序负整数。

练习 5：分析桶排序的最坏情况。构造一个输入，使桶排序退化成 Θ(n²)。

错误诊断

练习 6：以下场景能用计数排序吗？

场景	键类型	范围	n	能用吗？理由
年龄排序	整数	0-150	10^6
ID排序	整数	1-10^9	10^5
时间戳排序	整数	0-10^12	10^6
价格排序	浮点	0-1000	10^6

练习 7：agent 建议用基数排序处理浮点数。这个建议对吗？为什么？

方案比较

练习 8：比较三种线性排序：

维度	计数排序	基数排序	桶排序
时间复杂度
空间复杂度
是否稳定
键类型要求
分布要求

填完后，给出一个场景匹配建议。

开放设计

练习 9：设计一个"线性排序可行性检测"Skill。

输入：

• 键类型
• 键值范围 k
• 数据规模 n
• 输入分布（均匀？未知？）

输出：

• 能用哪种线性排序？
• 前提条件是否满足？
• 如果不满足，推荐什么？

---

上一节：3.4 堆排序

下一节：3.6 顺序统计量