学习笔记 数据结构与算法

基数排序（Radix Sort）

按位排序的线性时间算法

一、算法概述

基数排序（Radix Sort）是一种非比较型整数排序算法，其核心思想是按位排序——将整数按位数切割成不同的数字位，然后按每个位分别进行排序。基数排序属于分配式排序（Distribution Sort），通过键值的部分信息将要排序的元素分配至某些"桶"中，以达到排序的效果。

基数排序最早由IBM的Herman Hollerith在1887年用于打孔卡制表机（Tabulating Machine）中。这种机器通过读取打孔卡上不同位置的孔洞来对数据进行排序，其本质就是一种基数排序。在计算机诞生之前，基数排序就已经在商业数据处理中发挥了重要作用。

核心思想：

  • 将待排序元素按位数（digit）拆分为多个部分
  • 从某一位开始，对元素进行稳定排序
  • 逐位处理，直到所有位处理完毕
  • 最终得到完全有序的序列

基本术语

  • 基数（Radix/Base）：每一位数字的取值范围。十进制基数为10，二进制基数为2，ASCII码基数为256
  • 位数（Digit）：数字在某一数位上的值。十进制数123的个位为3，十位为2，百位为1
  • LSD（Least Significant Digit）：从最低位（最右边）开始排序
  • MSD（Most Significant Digit）：从最高位（最左边）开始排序
  • 稳定排序（Stable Sort）：相同值的元素在排序后保持原有相对顺序

基数排序之所以能在线性时间内完成排序，正是因为避开了基于比较的排序算法（如快速排序、归并排序等）的 O(n log n) 下限。它利用的基数和位数的特性，通过分配和收集的方式对数据排序。

二、LSD 基数排序（从最低位开始）

LSD（Least Significant Digit）基数排序是最常见的基数排序实现方式。它从数字的最低位（个位）开始，逐位向高位进行处理，每次使用一个稳定排序（通常是计数排序）对当前位进行排序。

算法步骤

  1. 确定待排序数组中的最大值，计算其位数 d
  2. 从低位到高位，依次处理每一位（个位、十位、百位...）
  3. 对每一位，使用计数排序（或其他稳定排序）进行排序
  4. 重复步骤3，直到最高位处理完毕

示例演示

以数组 [170, 45, 75, 90, 2, 802, 24, 66] 为例，演示 LSD 基数排序的完整过程：

// 原始数组 初始: [170, 45, 75, 90, 2, 802, 24, 66] // 第1轮：按个位（10^0）排序 按个位分配: 桶0: [170, 90] (个位为0) 桶2: [2, 802] (个位为2) 桶4: [24] (个位为4) 桶5: [45, 75] (个位为5) 桶6: [66] (个位为6) 收集后: [170, 90, 2, 802, 24, 45, 75, 66] // 第2轮：按十位（10^1）排序 按十位分配: 桶0: [2, 802] (十位为0) 桶2: [24] (十位为2) 桶4: [45] (十位为4) 桶6: [66] (十位为6) 桶7: [170, 75] (十位为7) 桶9: [90] (十位为9) 收集后: [2, 802, 24, 45, 66, 170, 75, 90] // 第3轮：按百位（10^2）排序 按百位分配: 桶0: [2, 24, 45, 66, 75, 90] (百位为0) 桶1: [170] (百位为1) 桶8: [802] (百位为8) 收集后: [2, 24, 45, 66, 75, 90, 170, 802] // 排序完成 ✓

从上述过程可以看出，每一轮排序只关注当前位的值，利用计数排序的稳定性，保证在后续高位排序时，低位已经排好的顺序不会被破坏。

LSD 的完整实现

以下是用 C 语言实现的 LSD 基数排序：

C 语言实现
// LSD 基数排序 - C 语言实现 #include <stdio.h> #include <stdlib.h> #include <string.h> // 使用计数排序对数组的指定位进行排序 void countingSortByDigit(int arr[], int n, int exp) { int* output = (int*)malloc(n * sizeof(int)); int count[10] = {0}; int i; // 统计当前位的出现次数 for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // 转换为累积位置 for (i = 1; i < 10; i++) count[i] += count[i - 1]; // 从后向前遍历，保证稳定性 for (i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // 将排序结果复制回原数组 for (i = 0; i < n; i++) arr[i] = output[i]; free(output); } // LSD 基数排序主函数 void radixSort(int arr[], int n) { // 找到最大值以确定位数 int maxVal = arr[0], exp; for (int i = 1; i < n; i++) if (arr[i] > maxVal) maxVal = arr[i]; // 从个位开始逐位排序 for (exp = 1; maxVal / exp > 0; exp *= 10) countingSortByDigit(arr, n, exp); }

Python 实现更为简洁：

Python 语言实现
def counting_sort_by_digit(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 # 统计当前位的出现次数 for i in range(n): digit = (arr[i] // exp) % 10 count[digit] += 1 # 转换为累积位置 for i in range(1, 10): count[i] += count[i - 1] # 从后向前构建输出数组（保持稳定性） for i in range(n - 1, -1, -1): digit = (arr[i] // exp) % 10 output[count[digit] - 1] = arr[i] count[digit] -= 1 # 复制回原数组 for i in range(n): arr[i] = output[i] def radix_sort(arr): if len(arr) == 0: return # 找到最大值 max_val = max(arr) # 从个位开始逐位排序 exp = 1 while max_val // exp > 0: counting_sort_by_digit(arr, exp) exp *= 10

可以看到，LSD 基数排序的核心在于嵌套了两层循环：外层循环遍历每一位（共 d 位），内层循环对当前位执行计数排序（O(n+k)）。由于计数排序是稳定排序，每轮排序后低位的顺序被完整保留到下一轮，最终得到全局有序序列。

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

MSD（Most Significant Digit）基数排序与 LSD 相反，它从数字的最高位开始排序。MSD 的排序过程是递归式的：先按最高位分组，再在每个分组内递归地对较低位进行排序。

算法步骤

  1. 找到数组中最大值的位数 d
  2. 从最高位（第 d-1 位）开始处理
  3. 将元素按当前位的值分配到不同的桶中
  4. 对每个桶递归地按下一位进行排序
  5. 当所有位处理完毕或桶中元素个数小于等于1时停止
  6. 将各个桶按顺序连接起来

MSD 的特点

  • 递归结构：每个桶独立递归排序，天然适合并行处理
  • 早期分治：最高位决定了元素的大致区间，能快速将数据分散
  • 桶内排序：桶内元素较少时，可切换到插入排序等简单排序进行优化
  • 空间开销：递归调用栈带来额外空间消耗
  • 应用场景：特别适合字符串排序和变长数据排序

MSD 与 LSD 的最重要区别在于：LSD 不需要递归，实现简单且稳定；MSD 需要递归处理每个桶，但能更早地分离不同区间的数据。对于字符串排序，MSD 尤其高效，因为短字符串可以提前结束递归，而 LSD 必须处理所有字符串的最大长度。

MSD 的 Python 实现

Python 语言实现（MSD）
def msd_radix_sort(arr, digit=None, base=10): if len(arr) <= 1: return arr # 第一次调用时确定最高位 if digit is None: max_val = max(arr) if max_val == 0: return arr digit = len(str(max_val)) - 1 # 按当前位分配到桶中 buckets = [[] for _ in range(base)] divisor = base ** digit for num in arr: digit_val = (num // divisor) % base buckets[digit_val].append(num) # 递归排序每个非空桶 if digit > 0: for i in range(base): if len(buckets[i]) > 1: buckets[i] = msd_radix_sort(buckets[i], digit - 1, base) # 连接所有桶 result = [] for bucket in buckets: result.extend(bucket) return result

MSD 基数排序的一个典型应用是字符串排序。对于字符串数组，将每个字符视为一位，基数设为字符集大小（如ASCII码的256），从第一个字符开始递归分组排序。这一算法在字符串处理领域非常高效。

四、时间复杂度分析

基数排序的时间复杂度分析需要考虑三个关键参数：

指标 复杂度 说明
最好情况 O(d(n+k)) 无论数据分布如何，都需要处理所有 d 位
最坏情况 O(d(n+k)) 与最好情况相同，无额外的比较开销
平均情况 O(d(n+k)) 稳定的线性时间，不依赖数据分布
空间复杂度 O(n+k) 需要计数数组和输出数组
稳定性 稳定 取决于内部使用的排序是否稳定

复杂度的深入理解

对于十进制整数排序，每个位上的计数排序复杂度为 O(n+10) = O(n)。若有 d 位，则总复杂度为 O(d·n)。当 d 为常数（例如32位整数 d=10）时，时间复杂度退化为 O(n)，实现了线性时间排序。

更一般地，如果排序的数字范围是 0 到 N，则位数 d = logkN（k 为基数），总时间复杂度为 O(n·logkN)。当 k 接近 N 时，logkN ≈ 1，O(n·logkN) ≈ O(n)，这时基数排序的性能最优。

与比较排序的对比

基数排序 vs 快速排序

快速排序等比较排序的理论下限为 O(n log n)。基数排序 O(d(n+k)) 在 d 较小（即数字范围不大）时明显优于 O(n log n)。但当 d 很大时，例如对64位整数排序，d=20（以10为基），基数排序也不一定比快速排序快。实际测试中，基数排序在数据量大且位数较少时优势明显。

五、基数选择与优化

基数的选择是基数排序中的一个重要权衡点。基数 k 越大，每轮处理的位数越少（d 变小），但每轮计数排序的开销更大（k 变大）。

常见基数选择

以256为基数的优化实现

在实际工程中，最常用的优化方式是将基数设为 256（一个字节的大小），这样可以将任何32位整数视为4个"位"（每个位是一个字节），只需4轮计数排序即可完成排序。

C 语言实现（256 基数优化版）
// 以256为基数的基数排序（使用位运算优化） #include <stdint.h> void radixSort256(uint32_t arr[], int n) { uint32_t* output = (uint32_t*)malloc(n * sizeof(uint32_t)); int count[256]; int shift, i; // 对 4 个字节分别排序（每个字节当作一位） for (shift = 0; shift < 32; shift += 8) { memset(count, 0, sizeof(count)); // 统计当前字节的出现次数 for (i = 0; i < n; i++) count[(arr[i] >> shift) & 0xFF]++; // 累积位置 for (i = 1; i < 256; i++) count[i] += count[i - 1]; // 稳定排序（从后向前遍历） for (i = n - 1; i >= 0; i--) { int byteVal = (arr[i] >> shift) & 0xFF; output[count[byteVal] - 1] = arr[i]; count[byteVal]--; } // 复制回原数组 for (i = 0; i < n; i++) arr[i] = output[i]; } free(output); }

上述实现使用了位运算来提取每个字节，避免了耗时的除法和取模运算。对于32位无符号整数，只需4轮遍历即可完成排序，效率极高。这是许多高性能排序库（如 NVIDIA CUDA 的 thrust 库）中使用的核心技术。

基数选择的经验法则

  • 对于32位整数，基数256通常是最优选择（4轮，256个桶）
  • 对于64位整数，可以考虑基数65536（4轮，65536个桶）或基数256（8轮，256个桶）
  • 对于字符串，基数取决于字符集大小（ASCII为128/256，Unicode需更大）
  • 基数越大，每轮内存访问的随机性越强，缓存局部性变差
  • 基数越小，轮数越多，但每轮的内存访问模式更线性

六、代码实现汇总

以下是基数排序在多种语言中的完整实现，便于读者对比学习：

Java 实现

Java 语言实现
public class RadixSort { public static void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; int[] count = new int[10]; for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, n); } public static void radixSort(int[] arr) { if (arr.length == 0) return; int maxVal = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; maxVal / exp > 0; exp *= 10) countingSortByDigit(arr, exp); } }

JavaScript 实现

JavaScript 语言实现
function radixSort(arr) { const maxVal = Math.max(...arr); let exp = 1; while (Math.floor(maxVal / exp) > 0) { countingSortByDigit(arr, exp); exp *= 10; } return arr; } function countingSortByDigit(arr, exp) { const n = arr.length; const output = new Array(n).fill(0); const count = new Array(10).fill(0); for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++; for (let i = 1; i < 10; i++) count[i] += count[i - 1]; for (let i = n - 1; i >= 0; i--) { const digit = Math.floor(arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } for (let i = 0; i < n; i++) arr[i] = output[i]; }

七、应用场景

基数排序虽然不是通用排序算法，但在特定场景下有非常出色的表现：

1. 整数排序

当需要排序的整数范围较大但位数有限时（如32位或64位整数），基数排序可以在 O(n) 时间内完成。这在大规模数据处理中尤其有价值。例如，在数据库系统的排序算子和外部排序中，基数排序作为第一阶段的分配策略，能快速将数据划分为有序的归并段。

2. 字符串排序

基数排序是字符串排序的经典算法。将每个字符看作一位，从第一个字符（MSD）开始递归排序。这也是 Unix 系统 sort 命令的核心算法之一。对于长度差异较大的字符串集合，MSD 基数排序配合插入排序（在短桶中切换）是最高效的字符串排序方案。

3. 日期排序

日期格式天然适合基数排序。将日期分解为年、月、日三个"位"，从日到年（LSD）或从年到日（MSD）进行排序。例如，对一组 YYYY-MM-DD 格式的日期排序：

// 将日期看作三位数：年(高位)、月、日(低位) 日期数组: [2024-03-15, 2023-12-01, 2024-01-20, 2023-06-10] 按 LSD 排序过程: 第1轮(日): [2023-12-01, 2024-03-15, 2024-01-20, 2023-06-10] 第2轮(月): [2024-01-20, 2023-06-10, 2023-12-01, 2024-03-15] 第3轮(年): [2023-06-10, 2023-12-01, 2024-01-20, 2024-03-15] ✓

4. GPU 并行排序

基数排序在GPU 并行计算领域得到了广泛应用。NVIDIA CUDA 的 thrust 库和 CUB 库都提供了高性能的基数排序实现。GPU 的海量并行线程可以同时对多个桶进行计数和分配，充分利用基数排序的可并行特性。

实际应用中的注意事项

  • 基数排序对负数和浮点数需要特殊处理（见下节）
  • 基数排序是非原地排序，需要额外的 O(n) 空间
  • 对于小规模数据（n < 1000），插入排序或快速排序通常更快
  • 基数排序的内存访问模式不够连续（尤其是基数较大时），可能导致缓存不命中

八、负数处理

基本的基数排序只能处理非负整数。当数组中包含负数时，标准的取模运算会产生负数索引，导致排序失败。以下是几种常见的负数处理策略：

策略一：偏移法（加常数）

将整个数组的元素加上最小值的绝对值，使所有元素变为非负数，排序后再减去该值。

Python 实现（偏移法处理负数）
def radix_sort_with_negatives(arr): if len(arr) == 0: return arr min_val = min(arr) # 偏移：所有元素加上最小值的绝对值 if min_val < 0: offset = -min_val for i in range(len(arr)): arr[i] += offset # 使用标准基数排序 radix_sort(arr) # 恢复原始值 if min_val < 0: for i in range(len(arr)): arr[i] -= offset return arr

策略二：符号位处理法

在按字节排序（基数256）时，可以将整数的符号位单独处理。对于有符号32位整数，其最高字节的最高位为符号位。可以通过反转符号位的方式，使负数按大小正确排列。

C 语言实现（符号位优化）
void radixSortSigned(int32_t arr[], int n) { // 将有符号整数转换为无符号（通过翻转符号位） uint32_t* uarr = (uint32_t*)arr; for (int i = 0; i < n; i++) uarr[i] ^= (uint32_t)1 << 31; // 翻转最高位 // 对无符号整数执行基数排序 radixSort256(uarr, n); // 使用前面定义的基数256版本 // 恢复符号位 for (int i = 0; i < n; i++) uarr[i] ^= (uint32_t)1 << 31; }

符号位处理法的原理是：在 IEEE 754 标准的整数表示中，正整数的最高位为0，负整数的最高位为1。翻转符号位后，负数（原最高位为1）变为正数（最高位为0），但负数的顺序恰好相反。不过，由于基数排序从最低字节开始（LSD），只需要确保每个字节内的顺序正确即可。

浮点数排序

IEEE 754 浮点数也可以通过类似的位变换技巧使用基数排序。只需将浮点数的位表示当作整数处理，并对负数的位模式进行特殊变换（翻转所有位），就可以直接使用整数基数排序对有符号浮点数进行排序。

九、与计数排序、桶排序的对比

基数排序与计数排序、桶排序同属于非比较排序家族，三者既有联系又有区别。

属性 计数排序 桶排序 基数排序
核心思想 统计每个值的出现次数 按值区间分桶，桶内再排序 按位分桶，逐位排序
时间复杂度 O(n+k) O(n+k) O(d(n+k))
空间复杂度 O(k) O(n+k) O(n+k)
适用场景 值范围小（k=O(n)） 数据均匀分布 数据位数少
稳定性 稳定 稳定 稳定
是否原地 否 否 否

三者关系

  • 计数排序适用于值范围较小的整数排序（如年龄、成绩）
  • 桶排序适用于均匀分布的数据（如0-1之间的浮点数），需要额外排序算法处理桶内数据
  • 基数排序是计数排序的泛化——它通过逐位处理将大范围的值拆解为小范围值的多次排序
  • 基数排序内部通常使用计数排序作为稳定排序的原子操作
  • 三者都不是基于比较的排序，都不受 O(n log n) 下限的限制

选型建议

  • 如果待排序数据的值域范围 k 较小（不超过 n 的线性倍数），优先考虑计数排序
  • 如果数据均匀分布且可用哈希函数映射到桶，考虑桶排序
  • 如果数据是大范围整数或字符串且位数有限，优先考虑基数排序
  • 如果数据规模较小（n < 1000），或者需要原地排序，考虑快速排序等比较排序
  • 在实际工程中，混合策略往往效果最佳——例如当桶内元素较少时从基数排序切换到插入排序

十、算法优化与工程实践

缓存优化

基数排序的一个主要性能瓶颈是缓存不命中。当基数较大（如256或65536）时，计数数组较大，每轮排序需要多次随机访问计数数组，容易导致缓存缺失。优化策略包括：

混合排序策略

在实际工程中，纯粹的基数排序并不总是最优选择。许多现代排序库（如 Rust 的排序实现、Python 的 TimSort）都采用混合策略：

混合排序策略示例（伪代码）
def hybrid_sort(arr): n = len(arr) if n <= THRESHOLD: # 小数据用插入排序 insertion_sort(arr) elif is_suitable_for_radix(arr): # 适合基数排序 radix_sort(arr) else: # 默认用快速排序 quick_sort(arr)

十一、核心要点总结

十二、进一步思考

练习与扩展

  • 实现一个支持负数和浮点数的通用基数排序函数
  • 比较基数排序与快速排序在不同数据规模（1万、10万、100万、1000万）下的实际运行时间
  • 尝试将 MSD 基数排序改造为多线程版本，观察并行加速比
  • 研究 GPU（CUDA/OpenCL）上的并行基数排序实现
  • 思考如何用基数排序的思想解决其他问题——例如在大数据量的 Top-K 问题中利用 MSD 快速分桶
  • 探索基数排序在后缀数组构建中的应用——基数排序是 DC3 等后缀数组线性时间构建算法的基石

"基数排序是少数能在线性时间内完成排序的算法之一。它巧妙地利用了数字的位置表示法，将看似需要全局比较的问题分解为局部位上的简单分配问题。理解基数排序，不仅是学会一种排序方法，更是理解'分而治之'思想在算法设计中的精妙应用。"