第8章 线性时间排序

导读

在前面的章节中，我们学习了基于比较的排序算法（如归并排序、堆排序、快速排序），它们的下界为Ω(n log n)。然而，通过放弃基于比较的策略，我们可以设计出在特定条件下达到O(n)时间复杂度的排序算法。本章将介绍计数排序、基数排序和桶排序这三种线性时间排序算法，并探讨它们各自的适用条件和局限性。

理解这些算法的关键在于认识到：不同的排序算法利用了输入数据的不同特性。基于比较的排序对数据分布没有任何假设，而线性时间排序则利用了数据的特定结构（如范围有限、位数固定、均匀分布等）。

核心概念详解

8.1 排序的下界定理

定理：任何基于比较的排序算法在最坏情况下至少需要Ω(n log n)次比较。

证明（决策树模型）：

• 将排序算法的执行过程表示为一棵二叉决策树
• 每个内部节点表示一次比较aᵢ:aⱼ
• 每个叶子节点表示一个排列
• 对于n个元素，有n!种可能的排列
• 因此决策树至少有n!个叶子
• 树的高度h ≥ log₂(n!) = Θ(n log n)
• 最坏情况比较次数 = 树的高度 = Ω(n log n)

这个下界定理告诉我们：要突破O(n log n)，必须放弃基于比较的策略。

8.2 计数排序

基本思想：

计数排序（Counting Sort）假设输入元素是范围在0到k之间的整数。对于每个输入元素x，确定小于x的元素个数，从而直接确定x在输出数组中的位置。

算法描述：

COUNTING-SORT(A, B, k)
    创建C[0..k]并初始化为0
    for i = 1 to A.length
        C[A[i]] = C[A[i]] + 1
    // C[i]现在包含值i的元素个数
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    // C[i]现在包含值≤i的元素个数
    for j = A.length downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

时间复杂度：O(n + k)

• 统计计数：O(n)
• 累加计数：O(k)
• 放置元素：O(n)

空间复杂度：O(n + k)

• 需要额外的计数数组C[0..k]
• 需要输出数组B[1..n]

稳定性：稳定排序。从后往前遍历保证了相等元素的相对顺序。

适用条件：

• 输入元素为整数
• k = O(n)时，时间复杂度为O(n)
• k远大于n时，效率不高

8.3 基数排序

基本思想：

基数排序（Radix Sort）按位排序。从最低位开始，依次对每一位使用稳定排序（通常是计数排序），直到最高位。

算法描述（以d位十进制数为例）：

RADIX-SORT(A, d)
    for i = 1 to d
        使用稳定排序按第i位对A排序

正确性证明（数学归纳法）：

• 归纳假设：在对前i-1位排序后，数组按前i-1位有序
• 归纳步骤：对第i位排序后，由于使用稳定排序，前i-1位的顺序在前i位相同时保持不变
• 因此，按前i位有序

时间复杂度：O(d(n + k))

• d为位数
• 每轮使用计数排序，时间为O(n + k)
• 总共d轮

常见变体：

• 十进制：d位，k=10，时间O(d(n+10))
• 二进制：d位，k=2，时间O(d(n+2))
• 按字节分组：每8位一组，d'=⌈d/8⌉，k=256

示例：

排序170, 45, 75, 90, 802, 24, 2, 66

按个位排序：170, 90, 802, 2, 24, 45, 75, 66

按十位排序：802, 2, 24, 45, 66, 170, 75, 90

按百位排序：2, 24, 45, 66, 75, 90, 170, 802

8.4 桶排序

基本思想：

桶排序（Bucket Sort）假设输入均匀分布在[0, 1)区间内。将[0, 1)分成n个等大小的桶，将元素分配到对应的桶中，然后对每个桶内部排序。

算法描述：

BUCKET-SORT(A)
    创建n个空桶B[0], B[1], ..., B[n-1]
    for i = 1 to n
        将A[i]放入桶B[⌊n·A[i]⌋]
    for i = 0 to n - 1
        对B[i]中的元素排序（通常用插入排序）
    按顺序合并各桶

时间复杂度分析：

• 分配元素到桶：O(n)
• 各桶内部排序：期望O(n)

- 每个桶中元素的期望个数为1

- n个桶，每个桶用插入排序，期望总时间为O(n)

• 合并：O(n)
• 总期望时间：O(n)

最坏情况：O(n²)

• 所有元素落入同一个桶
• 退化为插入排序

适用条件：

• 输入均匀分布
• 输入为[0, 1)区间的实数
• 可以推广到任意均匀分布的区间

8.5 三种算法的比较

8.6 计数排序的优化

空间优化：

当k很大但实际出现的值很稀疏时，可以使用哈希表代替数组来计数。

并行化：

• 将输入分成多个块
• 各块独立计数
• 合并计数结果
• 并行放置元素

与基数排序的结合：

当k很大时，可以先用基数排序将数据范围缩小，再用计数排序。

8.7 基数排序的实现细节

位的选择：

• 二进制位：简单但轮次多
• 字节（8位）：平衡轮次和每轮代价
• 更大的组：减少轮次但增加每轮计数数组大小

排序方向：

• 从最低位到最高位（LSD）：标准方法
• 从最高位到最低位（MSD）：可以提前终止

字符串排序：

基数排序也适用于字符串，从最右字符开始向左处理。

8.8 线性时间排序的局限性

虽然线性时间排序在特定条件下很快，但它们有严格的限制：

数据类型限制：计数排序和基数排序只适用于整数或可分解为位的数据

分布假设：桶排序假设均匀分布

空间开销：都需要额外的空间

通用性差：不能像比较排序那样适用于任意可比较的数据

8.9 实际应用中的选择

在实际工程中，选择排序算法需要考虑：

• 数据特征：整数还是实数？范围多大？分布如何？
• 性能要求：是否需要保证最坏情况？
• 空间限制：是否有足够内存？
• 稳定性要求：是否需要保持相等元素的顺序？

8.10 超越线性时间排序

除了本章介绍的三种算法，还有一些特殊的排序方法：

• 闪光排序（Flash Sort）：基于分布的排序，期望O(n)
• 平滑排序（Smoothsort）：自适应排序，对近乎有序的数据更快
• 样本排序（Sample Sort）：并行排序算法

重要知识点

知识点1：基于比较排序的下界

Ω(n log n)是基于比较排序的理论下界。这个下界的证明使用决策树模型，展示了比较排序的信息论极限。要突破这个下界，必须利用数据的额外信息。

知识点2：计数排序的稳定性

计数排序的稳定性来自于从后往前遍历输入数组。这保证了相等元素在输出中的相对顺序与输入中一致。稳定性对于基数排序的正确性至关重要。

知识点3：基数排序的正确性

基数排序的正确性依赖于内部排序的稳定性。数学归纳法证明了：在对第i位排序后，数组按前i位有序。这个性质保证了最终结果的正确性。

知识点4：桶排序的期望分析

桶排序的期望时间分析使用了指示器随机变量。每个桶中元素的期望个数为1，因此每个桶的插入排序期望时间为O(1)。n个桶的总期望时间为O(n)。

知识点5：空间-时间权衡

线性时间排序通常需要额外的空间：

• 计数排序：O(n+k)
• 基数排序：O(n+k)
• 桶排序：O(n)

这是用空间换时间的典型例子。

常见误区

误区1：线性时间排序可以替代所有排序算法

线性时间排序有严格的适用条件。在通用场景下，基于比较的排序（如快速排序、归并排序）仍然是更好的选择。

误区2：计数排序的k可以任意大

当k >> n时，计数排序的时间O(n+k)主要由k决定，效率不高。此时应考虑基数排序或其他方法。

误区3：基数排序总是比计数排序好

基数排序的时间为O(d(n+k))，当d很大时可能不如计数排序。选择取决于数据特征。

误区4：桶排序的最坏情况不重要

虽然桶排序的期望时间为O(n)，但最坏情况为O(n²)。在对性能有严格要求的场景中，需要考虑最坏情况。

误区5：线性时间排序不需要比较

计数排序和基数排序确实不需要直接比较元素，但它们利用了数据的数值信息。桶排序在桶内排序时仍然需要比较。

实践应用

应用1：后缀数组构建

后缀数组是字符串处理中的重要数据结构，其构建算法使用基数排序：

• DC3算法（Difference Cover 3）
• SA-IS算法（Suffix Array by Induced Sorting）
• 时间复杂度O(n)，使用基数排序作为子程序

应用2：图像处理

在图像处理中，像素值范围有限（0-255），适合使用计数排序：

• 直方图计算
• 直方图均衡化
• 颜色量化

应用3：数据库排序

数据库系统在处理整数键排序时使用线性时间排序：

• 索引构建
• 排序合并连接
• 外部排序的桶分配

应用4：网络数据包分类

路由器使用基数排序的变体对数据包进行分类：

• 按IP地址前缀匹配
• 多级路由表查找
• 硬件友好的并行实现

应用5：大数据排序

在大数据场景中，桶排序的思想用于分布式排序：

• 范围分区（Range Partitioning）
• 各分区独立排序
• 合并结果

8.11 排序下界的严格证明

决策树模型：

任何基于比较的排序算法都可以表示为一棵决策树：

• 每个内部节点标记为i:j，表示比较aᵢ和aⱼ
• 左分支表示aᵢ ≤ aⱼ，右分支表示aᵢ > aⱼ
• 每个叶子节点表示一个排列π
• 从根到叶子的路径表示算法对某个输入的执行过程

下界证明：

• 决策树必须有至少n!个叶子（每种排列对应一个叶子）
• 二叉树高度h与叶子数L的关系：L ≤ 2^h
• 因此n! ≤ 2^h，即h ≥ log₂(n!)
• 由斯特林近似：log₂(n!) = Θ(n log n)
• 最坏情况比较次数 = 树高 = Ω(n log n)

信息论解释：

排序需要从n!种可能排列中确定一种。每次比较最多提供1比特信息。因此至少需要log₂(n!) ≈ n log n次比较。

8.12 计数排序的并行化实现

并行计数排序：

将输入数组分成p个块

每个块独立计算计数数组

合并p个计数数组（逐元素求和）

计算前缀和

并行放置元素到输出数组

时间复杂度：O(n/p + k)，在p个处理器上。

GPU实现：

计数排序非常适合GPU并行化：

• 计数阶段：每个线程处理一个元素，使用原子操作更新计数
• 前缀和：使用并行前缀和算法
• 放置阶段：每个线程独立放置一个元素

8.13 基数排序的MSD变体

MSD基数排序（从最高位开始）：

与LSD不同，MSD从最高位开始排序：

按最高位分配到桶中

递归地对每个桶按下一位排序

优势：

• 可以提前终止：如果桶中只有一个元素或所有元素相同
• 对字符串排序特别高效
• 不需要处理所有位

劣势：

• 递归开销
• 桶的大小不均匀，可能导致负载不均衡

字符串排序的优化：

• 三向字符串基数排序：类似三路快速排序
• 按字符分组，减少桶的数量
• 利用字符串前缀的公共性

8.14 线性时间排序在实际系统中的选择指南

选择决策树：

数据是整数吗？
├── 是：范围多大？
│   ├── k = O(n)：计数排序
│   ├── k >> n但固定位数：基数排序
│   └── 范围不确定：先离散化再排序
└── 否：数据均匀分布吗？
    ├── 是：桶排序
    └── 否：使用比较排序（O(n log n)）

实际系统中的默认选择：

• 大多数语言的标准库使用比较排序（Timsort、Introsort等）
• 原因：通用性好，不需要对数据做假设
• 特殊场景才使用线性时间排序

性能基准测试：

对于100万个32位整数：

• 快速排序：约100ms
• 基数排序：约30ms
• 计数排序（k=10⁶）：约10ms

本章小结

本章深入介绍了三种线性时间排序算法。我们学习了：

排序下界定理：基于比较的排序至少需要Ω(n log n)次比较。决策树模型和信息论解释。要突破这个下界，必须利用数据的额外信息。

计数排序：适用于范围有限的整数，时间O(n+k)，空间O(n+k)，稳定。并行化和GPU实现。

基数排序：按位排序，使用稳定排序作为子程序，时间O(d(n+k))。LSD和MSD两种变体。

桶排序：假设均匀分布，将元素分配到桶中分别排序，期望时间O(n)，最坏O(n²)。

算法选择：根据数据特征选择合适的方法。实际系统中的选择决策树。

排序下界的严格证明：决策树模型、斯特林近似、信息论解释。

线性时间排序展示了算法设计中的一个重要原则：利用问题的特殊结构可以设计出更高效的算法。在实际应用中，了解数据的特征并选择合适的排序算法是优化性能的关键。

关键术语

思考题

设计一个算法，在O(n)时间内对n个范围在[1, n²]之间的整数排序。

证明：如果使用不稳定的内部排序，基数排序的结果可能不正确。

分析当桶排序的输入不是均匀分布时，性能如何变化。如何改进桶排序以适应非均匀分布？

比较计数排序和基数排序在以下场景中的适用性：n个32位整数、n个长度不超过10的字符串、n个范围在[0, 10⁶]的整数。