基数排序（Radix Sort）详解

多轮分配与收集的稳定排序

算法概念与应用场景

基数排序的原理

基数排序（Radix Sort）是一种**非比较型**整数排序算法。它的核心思想是将整数按**位数**（或字符串按字符）切割成不同的数字，然后按每个位数（或字符位置）分别进行排序。它依赖于一个稳定的内部排序算法（通常是计数排序）来处理每一位的排序。

基数排序主要有两种方式：

  • LSD (Least Significant Digit) 基数排序：从**最低位**（最右边）开始，依次处理到最高位。每一轮都根据当前位的数字将所有元素分配到对应的“桶”中，然后再按桶的顺序收集回来。这种方式比较常用。
  • MSD (Most Significant Digit) 基数排序：从**最高位**（最左边）开始。它会将数据根据最高位分到不同的桶中，然后对每个桶内的数据**递归地**进行次高位的排序。

应用场景

基数排序特别适用于以下场景：

  • 对**大规模整数**进行排序，尤其是当这些整数的位数（或最大值）相对较小时（如学号、电话号码、IP地址的整数表示）。
  • 对**字符串**进行排序（如单词字典序、文件名），此时可以将每个字符看作一个“位”。
  • 当需要**保持相等元素相对顺序**不变时（即需要稳定排序）。
  • 在数据量 `n` 很大，但数据的位数 `d` 相对较小，且基数 `k`（如十进制为10）可控的情况下，追求接近**线性时间复杂度** O(d·n)。

与其他排序算法的对比

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
基数排序 (Radix Sort) O(d·(n+k)) 或 O(d·n) O(d·(n+k)) 或 O(d·n) O(n+k) 稳定
计数排序 (Counting Sort) O(n+k) O(n+k) O(n+k) 稳定
快速排序 (Quick Sort) O(n log n) O(n²) O(log n) - O(n) 不稳定
归并排序 (Merge Sort) O(n log n) O(n log n) O(n) 稳定
堆排序 (Heap Sort) O(n log n) O(n log n) O(1) 不稳定

注：`n` 是元素个数，`d` 是最大元素的位数（或最大长度），`k` 是基数（如十进制为 10）。基数排序的时间复杂度严格来说是 O(d·(n+k))，因为内部通常用计数排序，但当 k 远小于 n 时，常简化为 O(d·n)。

示例数组

170
45
75
90
802
24
2
66

LSD 会先看个位 (0, 5, 5, 0, 2, 4, 2, 6)，MSD 会先看百位 (1, 0, 0, 0, 8, 0, 0, 0)。

LSD 基数排序流程

LSD（Least Significant Digit）基数排序是最常用的基数排序形式。它从整数的**最低有效位**（即个位）开始，逐位向左（十位、百位...）进行排序。每一轮排序都利用一个**稳定的**排序算法（通常是计数排序的变体）来根据当前位的数字将元素分配到 0 到 9 这 10 个桶中，然后按桶的顺序（0 号桶到 9 号桶）将元素收集回原数组。这个过程重复进行，直到最高位也被处理完毕。

排序过程详解

  1. 确定最大位数 d：找出数组中绝对值最大的数，确定它有多少位。所有数都按这个最大位数处理（不足的数前面可以看作是 0）。
  2. 按位循环 (从 exp=1 开始)：进行 d 轮迭代，每一轮处理一个位。`exp` 代表当前的位权（1 代表个位，10 代表十位，100 代表百位...）。
    • 分配 (Distribution)：遍历数组中的每个元素。计算该元素在当前位上的数字（例如，对于数字 170，个位是 0，十位是 7，百位是 1）。根据这个数字（0-9），将元素放入对应的桶中。桶内部需要保持元素的**进入顺序**（FIFO 或类似稳定结构）。
    • 收集 (Collection)：按桶的编号从小到大（0 号桶到 9 号桶），依次将每个桶中的元素取出，放回原数组（或一个临时数组）。因为桶内是稳定的，并且收集是按顺序的，所以这一轮结束后，数组就按当前位排好序了，并且保持了之前位的排序结果（稳定性）。
  3. 更新位权：将 `exp` 乘以 10，进入下一轮，处理更高一位。
  4. 完成：当处理完最高位后（`exp` 大于最大数的最高位权），排序完成。

交互式演示

初始数组:

桶 (Buckets): (点击下方按钮开始演示)

MSD 基数排序简介

MSD（Most Significant Digit）基数排序与 LSD 相反，它从**最高有效位**（最左边）开始进行排序。MSD 排序通常采用**递归**的方式。

排序过程

  1. 确定处理范围和当前位：从最高位开始，对整个数组（或子数组）进行处理。
  2. 分配：根据当前最高位的值，将元素分配到对应的桶中（例如，0-9 的桶）。
  3. 递归排序：对每个桶中包含**多于一个元素**的子数组，**递归地**调用 MSD 排序，但这次是针对**下一位**（右边一位）进行排序。只包含一个或零个元素的桶自然就是有序的。
  4. 收集：当所有递归调用返回后，按桶的顺序（0 到 9）将所有桶中的元素收集起来，形成当前范围内的有序序列。

MSD 与 LSD 的主要区别

  • 处理顺序：MSD 从最高位到最低位，LSD 从最低位到最高位。
  • 实现方式：MSD 通常是递归的，需要处理子问题；LSD 是迭代的，每轮处理整个数据集。
  • 适用性：
    • MSD 对**字符串排序**可能更自然，因为字符串的前缀差异可以直接决定顺序，可能提前结束递归。
    • MSD 对于整数位数差异很大的情况可能效率不高，因为它需要处理很多递归层级。
    • LSD 实现相对简单，对于位数接近的整数通常表现稳定。
  • 空间开销：MSD 的递归调用栈可能带来额外的空间开销，而 LSD 的空间主要是桶和临时数组。
  • 缓存性能：LSD 的迭代访问模式通常比 MSD 的递归访问模式具有更好的缓存局部性。

MSD 第一轮划分示例

假设我们对数组 `[170, 45, 75, 90, 802, 24, 2, 66]` 进行 MSD 排序（假设最大 3 位）。

第一轮 (百位):

  1. 根据百位数字 (1, 0, 0, 0, 8, 0, 0, 0) 分配到桶：
    • 桶 0: [45, 75, 90, 24, 2, 66]
    • 桶 1: [170]
    • 桶 8: [802]
    • 其他桶为空
  2. 递归处理桶 0：对 `[45, 75, 90, 24, 2, 66]` 应用 MSD 排序（看十位）。
  3. 桶 1 和 桶 8 只有一个元素，递归结束。
  4. 收集结果：(递归排序后的桶 0) + [170] + [802]

这个过程会递归下去，直到所有子数组都被排序。

170
45
75
90
802
24
2
66

MSD 关注最高位进行首次划分。

时间 & 空间复杂度分析

时间复杂度: O(d·(n+k)) 或 O(d·n)

基数排序的时间复杂度主要取决于三个因素：

  • n: 待排序元素的个数。
  • d: 最大元素的位数（或字符串的最大长度）。对于数值，d ≈ logk(max_value)。
  • k: 基数（或桶的数量）。对于十进制整数是 10，对于 ASCII 字符可以是 128 或 256。

每一轮排序（共 d 轮），都需要遍历 n 个元素进行分配，并遍历 k 个桶进行收集。如果使用计数排序作为内部排序，每轮的时间复杂度是 O(n+k)。因此，总时间复杂度为 O(d·(n+k))。

在很多情况下，k 是一个常数（如十进制 k=10）或者 k 相对于 n 较小（k ≪ n），此时复杂度可以简化为 O(d·n)。

关键点：基数排序的时间复杂度是**线性的**（相对于 n），前提是 d 不太大。如果 d 非常大（例如，数字非常大，d ≈ n），则性能可能不如 O(n log n) 的比较排序。

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

基数排序需要额外的存储空间：

  • 桶 (Buckets)：需要 k 个桶来存放临时的元素。在最坏情况下，所有元素可能落入同一个桶，所以桶（或用于模拟桶的数据结构）需要能容纳 n 个元素。一种常见的实现是用计数排序的思路，需要一个大小为 k 的计数数组 `count[k]`。
  • 临时数组 (Output Array)：为了方便收集操作并保持稳定性，通常需要一个与原数组大小相同的临时数组，用于存放一轮排序后的结果。这需要 O(n) 的空间。

因此，总的空间复杂度是 O(n + k)。

稳定性

基数排序是**稳定**的排序算法。这是因为它依赖的内部排序（如计数排序）必须是稳定的。在每一轮按位排序时，如果两个元素当前位相同，它们在桶中的相对顺序以及收集回数组后的相对顺序，都与它们进入这一轮时的相对顺序保持一致。这保证了具有相同值的元素在排序后其原始的相对顺序不变。

复杂度对比图

上图示意了在 d 固定时，O(d·n) 相比 O(n log n) 的增长趋势。

优缺点总结

优点缺点
✅ 当 d 较小时，时间复杂度接近线性 O(n)，非常快。 ❌ 需要额外的 O(n+k) 空间，空间开销较大。
✅ 稳定排序。 ❌ 对于位数 d 非常大的情况，性能可能不如 O(n log n) 算法。
✅ 实现相对直观（尤其是 LSD）。 ❌ 不适用于无法按“位”拆分的数据（如浮点数需要特殊处理）。
✅ 适用于特定类型数据（整数、字符串）的大规模排序。 ❌ 对基数 k 的选择会影响性能。

基数排序 - 知识测验

请选择你认为正确的答案。点击选项后会显示反馈。

1. LSD 基数排序在每一轮按位排序时，通常依赖于哪种**稳定**的排序算法作为其核心子过程？
A. 快速排序 (Quick Sort)
B. 计数排序 (Counting Sort)
C. 堆排序 (Heap Sort)
D. 选择排序 (Selection Sort)
解析：基数排序的稳定性要求其内部按位排序的算法也是稳定的。计数排序是稳定且时间复杂度为 O(n+k) 的算法，非常适合用于基数排序的每一轮。快速排序、堆排序、选择排序通常是不稳定的。

进度: 1 / 5

基数排序编程练习 (C++)

练习 1：实现基本的 LSD 基数排序

请根据 LSD 基数排序的原理，实现一个 C++ 函数 `void radixSort(vector& arr)`，该函数能对一个包含**非负整数**的 `vector` 进行原地排序。

要求：

  • 使用 LSD 方式（从个位开始）。
  • 处理十进制整数。
  • 确保排序是稳定的。
  • 考虑如何确定最大位数或最大值。
  • 使用计数排序作为每一轮的内部排序方法。
// 函数签名
#include <vector>
#include <algorithm> // 用于 max_element
#include <cmath>     // 用于 pow
using namespace std;

void radixSort(vector& arr);

练习 2：扩展基数排序以支持负数

标准的基数排序通常直接处理非负整数。请思考如何修改或扩展基数排序算法，使其能够正确地对包含**负数和正数**的整数数组进行排序。

提示：

  • 一种常见的方法是将所有负数和正数分开处理。例如，可以先将所有负数取绝对值排序，然后反转，再将正数排序，最后合并。但这可能不优雅。
  • 另一种更统一的方法是：找到数组中的最小值 `minVal`。如果 `minVal` 是负数，则将数组中的**所有**元素都加上 `abs(minVal)`，使得它们都变为非负数。然后对这个“偏移后”的数组进行标准的基数排序。最后，将排序结果中的每个元素再减去 `abs(minVal)`，恢复其原始值。
  • 思考这种偏移方法是否会影响排序的正确性和稳定性。
// 思考如何修改 radixSort 或设计一个新的函数
void radixSortWithNegatives(vector& arr);

基数排序注意事项与优化

实现时的关键点

  • 确定最大值/最大位数 (d)：
    • 需要先遍历一次数组找到最大值 `maxVal`，然后确定其位数 `d` (可以通过 `log10(maxVal) + 1` 或循环除以 10 计算)。这是 O(n) 的预处理。
    • 或者，可以迭代进行轮次，直到所有数字在当前位及更高位都为 0 时停止。
  • 处理不同位数的数字：LSD 排序天然能处理不同位数的数字。较短的数字在高位会被当作 0 处理。例如，在处理百位时，数字 45 会被看作 045，其百位是 0。
  • 内部排序的稳定性：每一轮按位排序**必须**使用稳定的排序算法（如计数排序）。如果内部排序不稳定，最终结果将是错误的。计数排序实现时，通过累加计数数组来确定输出位置是保证稳定性的关键。
  • 基数 k 的选择：
    • 对于十进制整数，k=10 是自然的选择。
    • 对于二进制数据或需要按字节处理时，k=256 (28) 可能更高效，因为它能一次处理 8 位，减少轮数 d，但需要更大的计数数组和桶空间 (O(n+256))。
    • 选择过大的 k 会增加空间复杂度和每轮的常数时间，选择过小的 k 会增加轮数 d。需要权衡。
  • 负数处理：如练习 2 所述，需要特殊处理，例如通过偏移量将所有数映射到非负域。
  • 浮点数处理：基数排序不直接适用于浮点数。需要将其位表示（如 IEEE 754）解释为整数进行排序，并特别注意符号位和 NaN/无穷大等情况，比较复杂。

性能陷阱与优化考虑

  • d 过大：当数字范围极大，导致位数 d 很大时（例如 d ≈ n 或 d >> log n），O(d·n) 的性能可能劣于 O(n log n) 的比较排序。
  • 空间开销：O(n+k) 的额外空间可能成为瓶颈，尤其是在内存受限的环境下。
  • 缓存效率：LSD 排序中对数组的多次遍历访问模式通常比较缓存友好。MSD 的递归访问可能导致缓存未命中增多。
  • 原地排序?：严格意义上的基数排序（使用计数排序作为子过程）需要 O(n+k) 的额外空间，不是原地排序。有些变体尝试减少空间，但可能牺牲稳定性或增加复杂度。
  • 小数据量：对于非常小的数据集，O(n log n) 排序（如快速排序的常数因子可能更小）或者更简单的 O(n²) 排序（如插入排序）可能反而更快。

代码实现细节

  • 获取特定位：计算数字 `num` 的第 `exp` 位（`exp` 是 1, 10, 100...）通常用 `(num / exp) % 10`（对于基数 10）。
  • 计数排序实现：标准步骤是：计算频率 -> 计算累积频率（确定位置）-> 反向遍历原数组填充输出数组 -> 复制回原数组。

知识延伸与相关技术

基数排序在特定场景的应用

  • 字符串排序：
    • 可以将每个字符视为一个“位”。基数 k 可以是字符集的大小（如 ASCII 的 128 或 256）。
    • MSD 基数排序对字符串通常更自然，因为可以根据前缀不同提前结束递归。
    • 需要处理不同长度的字符串（例如，较短的字符串可以认为后面填充了某种特殊空字符）。
  • IP 地址排序：IPv4 地址可以看作一个 32 位整数，可以按字节（每字节 8 位，k=256）进行 4 轮基数排序，非常高效。
  • 处理复合键：如果需要按多个字段排序（例如，先按年龄，再按姓名），可以将字段组合成一个大的“数字”或依次进行多轮稳定的基数排序。

外部排序与分布式基数排序

  • 外部排序 (External Sorting)：当数据量大到无法完全载入内存时，需要使用外部排序。基数排序可以适用于外部排序场景。每一轮的分配和收集可以分块读写磁盘文件来完成。
  • 分布式基数排序：在分布式计算环境（如 MapReduce、Spark）中，基数排序的思想可以被用来实现大规模并行排序。例如，可以根据数据的某个范围或高位将其分发到不同的计算节点，节点内部排序后再合并。

与其他排序算法的关联与比较

  • 与计数排序 (Counting Sort)：
    • 基数排序可以看作是多轮的计数排序。
    • 计数排序是基数排序的基础，用于处理每一位的排序。
    • 计数排序适用于整数范围 k 不大的情况 (O(n+k))，而基数排序通过多轮处理扩展了其适用范围。
  • 与桶排序 (Bucket Sort)：
    • 两者都使用了“桶”的概念。
    • 桶排序假设输入数据均匀分布，将数据分配到有限数量的桶里，然后对每个桶内部使用其他排序方法（如插入排序）。
    • 基数排序的“桶”是根据特定位的值来分配的，桶的数量是固定的（等于基数 k）。
    • 可以说基数排序是桶排序的一种特殊形式或应用。

进一步学习

  • 研究 MSD 基数排序的递归实现细节和优化（如三向切分）。
  • 了解如何处理浮点数的基数排序。
  • 探索不同基数 k 对性能的具体影响。
  • 阅读并行和分布式基数排序的算法论文或实现。