基数排序：打破比较下界的正确姿势

每个学过算法的人都听过这样一句话：基于比较的排序算法，时间复杂度的下界是 O(n log n)。这个结论在理论上无懈可击，在实践中也被反复验证。然而，基数排序（Radix Sort）的存在似乎在挑战这个结论——它可以在 O(nk) 的时间内完成排序，其中 k 是键的位数。

这不是魔法，也不是悖论。理解基数排序为什么能「打破」下界，以及它在什么场景下真正有价值，是区分算法初学者和工程实践者的一道分水岭。本文将从决策树模型出发，深入基数排序的理论基础、工程实现、性能陷阱和实际应用场景，给出一个系统性的分析。

一、比较排序的 O(n log n) 下界证明

1.1 决策树模型

比较排序的下界证明建立在决策树（Decision Tree）模型之上。这个模型的核心假设是：排序算法获取元素间关系的唯一手段是两两比较。

对于 n 个不同元素的排列，共有 n! 种可能的排列方式。每一种排列对应一种不同的输入顺序，排序算法需要将其映射到唯一的有序输出。在决策树中，每个内部节点代表一次比较操作（如 a[i] <= a[j]），每个叶子节点代表一种最终排列。

                    a[0] <= a[1]?
                   /              \
              Yes /                \ No
               /                    \
        a[1] <= a[2]?          a[0] <= a[2]?
        /          \            /          \
      Yes          No         Yes          No
      /              \        /              \
  [0,1,2]    a[0]<=a[2]?  [1,0,2]    a[1]<=a[2]?
              /      \                  /      \
            Yes      No              Yes      No
            /          \            /          \
        [0,2,1]    [2,0,1]    [1,2,0]    [2,1,0]

上面是 3 个元素排序的完整决策树。3! = 6 种排列，对应 6 个叶子节点。

1.2 下界推导

决策树必须有至少 n! 个叶子节点，才能区分所有可能的输入排列。一棵高度为 h 的二叉树最多有 2^h 个叶子，因此：

2^h >= n!
h >= log2(n!)

利用 Stirling 近似：

log2(n!) = n*log2(n) - n*log2(e) + O(log n)
         ≈ n*log2(n) - 1.443*n
         = Θ(n log n)

这意味着在最坏情况下，任何比较排序算法至少需要 Θ(n log n) 次比较。这不是某个特定算法的限制，而是整个比较排序模型的信息论下界。

1.3 信息论视角

从信息论的角度看，排序本质上是一个信息获取过程。输入排列的不确定性（熵）是 log2(n!) 比特。每次比较最多获取 1 比特信息（是或否）。因此，至少需要 log2(n!) 次比较才能消除所有不确定性，确定输入的准确排列。

信息熵 = log2(n!) ≈ n*log2(n) - 1.443*n 比特
每次比较获取 <= 1 比特
所需比较次数 >= n*log2(n) - 1.443*n

这个分析优雅而有力，但它有一个容易被忽视的前提：它只适用于通过两两比较获取信息的模型。

二、基数排序不违反下界的原因

2.1 计算模型的边界

决策树下界的证明假设算法只能通过比较两个元素来获取信息。但这个假设并非宇宙法则——它只是一种计算模型的约束。

基数排序根本不比较元素。它直接读取元素的数字表示（二进制位或十进制位），然后根据这些位的值将元素分配到桶中。这就像邮局分拣信件：不需要逐一比较两封信的地址，只需看邮编的每一位数字，分到对应的格子里。

比较排序模型：
  信息来源 = 两两比较 (a[i] < a[j]?)
  每步信息量 = 1 比特
  下界 = Ω(n log n)

基数排序模型：
  信息来源 = 直接读取键的位 (digit(a[i], k))
  每步信息量 = log2(radix) 比特
  复杂度 = O(d * (n + radix))

2.2 代价的转移

基数排序没有违反任何定律，它只是把代价从「比较次数」转移到了「键的表示长度」上。如果我们把键看作 d 位的 radix 进制数，基数排序的时间复杂度是 O(d * (n + radix))。

关键问题是：d 到底有多大？

对于 n 个不同的整数，至少需要 log2(n) 位来区分它们。如果 d = O(log n) 且 radix = O(n)，基数排序的时间复杂度是 O(n)——看起来打破了 O(n log n) 的下界。

但这里有一个微妙之处：如果元素值域很大（比如 64 位整数），那么 d = 64/log2(radix)。当 radix = 256 时，d = 8；当 n < 2^64 时，这确实可能优于 O(n log n)。但如果 n 相对于值域很小，基数排序的常数因子和缓存不友好性可能抵消理论优势。

2.3 没有免费的午餐

基数排序的「免费性」有严格的条件：

1. 键必须可以被分解为固定数量的「位」。
2. 每一位的取值范围有限（基数有限）。
3. 键的位数 d 不能随 n 增长太快。

如果键是任意精度的实数，或者键的长度随 n 对数增长（如字符串的平均长度为 O(log n)），基数排序退化为 O(n log n)，和比较排序的下界一样。

我个人认为，这是算法理论中最容易被误解的地方之一。很多人以为基数排序「证明了」O(n log n) 不是排序的绝对下界，但实际上它只是在不同的计算模型下工作。在比较模型中，O(n log n) 仍然是不可逾越的。

三、MSD vs LSD 基数排序

基数排序有两种主要变体：LSD（Least Significant Digit）和 MSD（Most Significant Digit）。它们的区别不仅仅是处理方向，还涉及稳定性、内存使用、缓存行为和递归结构等多个维度。

3.1 LSD 基数排序

LSD 从最低有效位开始，逐步向最高有效位处理。每一轮对所有元素按当前位进行稳定排序（通常使用计数排序），经过 d 轮后整个数组有序。

输入: [170, 045, 075, 090, 002, 024, 802, 066]

Pass 1 (个位): [170, 090, 002, 802, 024, 045, 075, 066]
Pass 2 (十位): [002, 802, 024, 045, 066, 170, 075, 090]
Pass 3 (百位): [002, 024, 045, 066, 075, 090, 170, 802]

LSD 的正确性依赖于一个关键性质：每一轮使用的子排序必须是稳定的。如果第 i 轮是稳定的，那么第 i-1 轮建立的相对顺序不会被破坏。归纳下去，d 轮之后所有位都参与了排序，结果正确。

3.2 MSD 基数排序

MSD 从最高有效位开始，先按最高位把数据分到不同的桶里，然后对每个桶递归地按下一位排序。

输入: [170, 045, 075, 090, 002, 024, 802, 066]

Pass 1 (百位):
  桶0: [045, 075, 090, 002, 024, 066]
  桶1: [170]
  桶8: [802]

对桶0递归 Pass 2 (十位):
  桶0: [002]  桶2: [024]  桶4: [045]
  桶6: [066]  桶7: [075]  桶9: [090]

合并: [002, 024, 045, 066, 075, 090, 170, 802]

3.3 核心差异对比

3.4 选择建议

LSD 适合的场景： - 固定长度的键（32 位整数、64 位整数）。 - 需要稳定排序的场景。 - 键的位数较少，d 较小。

MSD 适合的场景： - 变长字符串排序（如字典序排序）。 - 数据分布不均匀，大部分数据可在前几位区分。 - 需要就地排序（如 American Flag Sort）。 - 需要提前终止的场景。

四、计数排序作为基础

4.1 计数排序回顾

基数排序的每一轮本质上是一次计数排序（Counting Sort）。计数排序是基数排序的基石，理解它的性能特征对优化基数排序至关重要。

// 计数排序：对数组 arr 按第 digit_pos 位排序
// radix 是基数（桶的数量）
void counting_sort_by_digit(int *arr, int *output, int n,
                            int digit_pos, int radix)
{
    int *count = calloc(radix, sizeof(int));

    // 第一遍：统计每个桶的元素数量
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / digit_pos) % radix;
        count[digit]++;
    }

    // 前缀和：计算每个桶的起始位置
    for (int i = 1; i < radix; i++) {
        count[i] += count[i - 1];
    }

    // 第二遍：从后向前遍历，保证稳定性
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / digit_pos) % radix;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    free(count);
}

4.2 基数（桶数量）的选择

基数（radix）的选择是基数排序中最关键的工程决策之一。它直接影响排序的轮数、内存使用和缓存行为。

设排序 n 个 W 位整数，选择基数 r = 2^b（按 b 位分组）：

轮数 d = W / b
每轮时间 = O(n + 2^b)
总时间 = O(W/b * (n + 2^b))

当 2^b <= n（即 b <= log2(n)）时，每轮时间简化为 O(n)，总时间为 O(nW/b)。为了最小化总时间，应该让 b 尽可能大，但不超过 log2(n)。

最优基数 r ≈ n
最优位数 b ≈ log2(n)
最优总时间 = O(nW / log n)

实践中常见的选择：

256（8 位）是最常见的选择，原因如下：

1. 对 32 位整数只需 4 轮，64 位整数只需 8 轮。
2. 计数数组大小仅 256 * sizeof(int) = 1 KB，轻松放入 L1 缓存。
3. 提取一个字节的操作在所有架构上都很高效。

但当 n 很大时（比如 n > 100 万），使用 16 位基数（65536 个桶）可以把 32 位整数的排序轮数从 4 减少到 2，代价是计数数组增大到 256 KB。是否值得取决于 n 的大小和缓存层级的容量。

4.3 前缀和的并行化潜力

计数排序中的前缀和步骤可以用 SIMD 指令并行化（Blelloch scan 思路），对大基数尤其有效。详见本系列第 113 篇：SIMD 算法设计模式。

五、缓存友好性问题

5.1 基数排序的内存访问模式

基数排序最大的实践问题不是时间复杂度，而是缓存性能。让我们分析 LSD 基数排序的内存访问模式：

第一遍（计数）：
  顺序读取 arr[0], arr[1], ..., arr[n-1]  // 顺序访问，缓存友好
  随机写入 count[digit]                     // 写入 count 数组，通常在 L1

第二遍（分配）：
  顺序读取 arr[n-1], arr[n-2], ..., arr[0]  // 反向顺序，仍可预取
  随机写入 output[count[digit] - 1]          // 写入位置几乎随机！

第二遍的写入是关键瓶颈。根据当前位的数字值，元素被写入输出数组的不同位置。如果数据在当前位上分布均匀，这些写入位置几乎是随机的——完全破坏了空间局部性。

5.2 缓存未命中的代价

对于 n = 100 万个 32 位整数，使用基数 256：

输出数组大小 = 4 MB
L1 缓存典型大小 = 32-48 KB
L2 缓存典型大小 = 256 KB - 1 MB
L3 缓存典型大小 = 4-32 MB

每轮散射写入导致的缓存未命中：
  如果输出数组 > L3：几乎每次写入都 miss（灾难级）
  如果输出数组在 L3 内：miss 率取决于关联度
  如果输出数组在 L2 内：miss 率较低

当 n 很大时，每轮基数排序都会对输出数组产生大量缓存未命中。这些 miss 是写 miss（write miss），在现代 CPU 上通常比读 miss 更昂贵，因为涉及缓存行的分配和写回。

5.3 与比较排序的对比

对比一下 pdqsort（Quicksort 变体）的内存访问模式：

pdqsort:
  - 分区操作：两个指针从两端向中间扫描，交换元素
  - 访问模式：几乎完全顺序
  - 递归后子问题变小，很快放入缓存
  - 缓存利用率极高

基数排序（LSD）:
  - 每轮对全数组做散射写入
  - 访问模式：读顺序，写随机
  - 全局操作，不缩小问题规模
  - 缓存利用率低

这就是为什么在实际基准测试中，基数排序在 n 较小（< 几万）时常常输给 pdqsort。理论上的 O(n) vs O(n log n) 在缓存不友好的常数因子面前显得苍白。

5.4 改善缓存行为的策略

有几种方法可以改善基数排序的缓存行为：

策略一：减小问题规模后切换。 当子数组足够小（能放入 L1 或 L2 缓存）时，切换到插入排序。MSD 基数排序天然支持这种策略。

策略二：软件预取。 在散射写入之前，用 __builtin_prefetch 预取即将写入的缓存行。需要提前若干步预取（PREFETCH_DISTANCE 通常设为 8-16），给内存子系统足够的延迟来响应。

策略三：分块处理（Blocked Radix Sort）。 将输入分成 cache-sized 块，先在每个块内统计桶计数，全局前缀和后再做散射。可以提高计数阶段的局部性，但散射写入仍然不友好。

六、ska_sort：缓存友好的基数排序

6.1 American Flag Sort

在讨论 ska_sort 之前，需要先了解 American Flag Sort（AFS）。AFS 是一种就地（in-place）的 MSD 基数排序变体，由 McIlroy、Bostic 和 McIlroy 在 1993 年提出。

AFS 的核心思路：不使用辅助数组，而是通过交换将元素移到正确的桶中。

输入: [170, 045, 075, 090, 002, 024, 802, 066]
按百位排序：

1. 第一遍：计数
   count[0]=6, count[1]=1, count[8]=1

2. 前缀和 -> 桶边界
   边界: [0, 6, 7, 8]  // 桶0占位置0-5，桶1占位置6，桶8占位置7

3. 就地交换：扫描每个桶区域，如果元素不属于当前桶，
   与它应该去的桶的下一个空位置交换

AFS 避免了 O(n) 的辅助数组，但它不是稳定排序。

6.2 ska_sort 的设计思路

ska_sort 是 Malte Skarupke 在 2016 年提出的一种缓存友好的基数排序实现。它基于 American Flag Sort，但做了若干关键优化：

1. 自适应基数选择：根据数据类型和分布自动选择最优基数。
2. 小数组回退：当子数组小于阈值时切换到 std::sort。
3. 就地分区：使用类似 AFS 的就地交换，避免辅助数组。
4. 类型萃取：通过模板特化支持不同的数据类型。

6.3 ska_sort 的核心算法

ska_sort 的就地分区过程可以概括为循环排列（cycle sort）的推广：先计数确定桶边界，然后扫描每个桶区域，把不属于当前桶的元素沿着「它应该去的桶」形成的链循环交换，直到链闭合。完整的 C 实现见 9.3 节。

6.4 ska_sort 的缓存优势

ska_sort 相比传统 LSD 基数排序的缓存优势来自两个方面：

1. 就地操作：不需要 O(n) 的辅助数组，内存使用量减半，空间局部性更好。

2. MSD 结构：递归处理子桶时，子问题迅速缩小。对 100 万个 32 位整数，第 1 轮处理全部 4 MB 数据，第 2 轮约 256 个子数组平均 16 KB（多数在 L1 内），第 3 轮后完全在缓存中完成。而 LSD 每轮都要对全数组做随机写入。

6.5 ska_sort 的局限

ska_sort 并非万能：不稳定排序（就地交换破坏相对顺序），实现复杂度高，对已有序数据无特别优化，模板机制增加编译开销。

七、为什么数据库排序不用基数排序

7.1 变长键问题

数据库中最常见的排序键是字符串——VARCHAR 类型。字符串的长度不固定，从几个字节到几千字节不等。

基数排序处理变长键有两种方式，都不完美：

方式一：填充到最大长度
  "cat"    -> "cat\0\0\0\0\0\0\0"
  "catalog" -> "catalog\0\0\0"
  问题：如果最大长度是 255 字节，大量短字符串浪费时间在填充位上

方式二：MSD + 特殊处理空字符
  把空字符（字符串结束）视为最小值
  递归时检查是否到达字符串末尾
  问题：递归深度等于最长字符串长度，极端情况下很深

相比之下，比较排序只需要一个字符串比较函数，遇到不同字符时立即返回，平均只需比较前几个字符。这种「提前终止」的能力是比较排序在变长键上的天然优势。

7.2 复合键和比较语义

数据库的 ORDER BY 经常涉及多个列和复杂的比较语义：

SELECT * FROM orders
ORDER BY region ASC, priority DESC, created_at ASC
COLLATE utf8mb4_unicode_ci;

这个查询涉及： - 三个不同类型的键（字符串、整数、时间戳）。 - 不同的排序方向（升序和降序混合）。 - 特定的字符串排序规则（Unicode collation）。

基数排序要处理这种场景，需要： 1. 将复合键编码为可按字节比较的二进制串。 2. 降序字段需要按位取反。 3. Unicode collation 需要先转换为排序键（sort key），这本身就是昂贵的操作。

比较排序只需要一个自定义的比较函数就能处理所有这些情况。

7.3 内存约束

数据库排序经常面临严格的内存限制。当数据量超过内存时，需要使用外部排序（External Sort），将数据分成可管理的块在磁盘上归并。

外部排序天然适合基于比较的归并排序，因为归并操作是顺序访问的。基数排序的散射写入模式对磁盘来说是灾难性的。

7.4 实际数据库的选择

注意 ClickHouse 的例外——它是列式存储数据库，排序键通常是固定长度的整数或日期类型，正是基数排序的最佳场景。这不是偶然的。

八、基数排序的实际最佳场景

基数排序并非通用排序的替代品，但在以下几类场景中几乎无可匹敌。完整的 C 实现见第九节。

8.1 整数数组排序

32 位 / 64 位整数是基数排序的经典目标。使用基数 256（按字节分组），32 位整数只需 4 轮，每轮 O(n)。有符号整数需要在最高字节排序时翻转符号位的解释顺序——补码中 0x80-0xFF 是负数，前缀和时先累计负数桶再累计正数桶即可。详见 9.1 节的完整实现。

8.2 浮点数排序

IEEE 754 浮点数有一个有趣的性质：如果把正浮点数的位模式解释为无符号整数，它们的大小顺序是一致的。负浮点数需要翻转所有非符号位。

/*
 * 浮点数到可排序整数的转换
 * 利用 IEEE 754 的位模式性质
 */
static inline uint32_t float_to_sortable(float f)
{
    uint32_t bits;
    memcpy(&bits, &f, sizeof(bits));

    // 如果是负数（符号位为1），翻转所有位
    // 如果是正数（符号位为0），只翻转符号位
    uint32_t mask = -(bits >> 31) | 0x80000000u;
    return bits ^ mask;
}

static inline float sortable_to_float(uint32_t bits)
{
    uint32_t mask = ((bits >> 31) - 1) | 0x80000000u;
    bits ^= mask;
    float f;
    memcpy(&f, &bits, sizeof(f));
    return f;
}

void radix_sort_float(float *arr, int n)
{
    uint32_t *data = malloc(n * sizeof(uint32_t));
    if (!data) return;

    // 转换为可排序的整数表示
    for (int i = 0; i < n; i++) {
        data[i] = float_to_sortable(arr[i]);
    }

    // 使用无符号整数基数排序
    radix_sort_uint32(data, n);

    // 转换回浮点数
    for (int i = 0; i < n; i++) {
        arr[i] = sortable_to_float(data[i]);
    }

    free(data);
}

8.4 固定长度字符串

对于固定长度的字符串（如 MD5 哈希、UUID、IP 地址），MSD 基数排序特别高效：

/*
 * MSD 基数排序：固定长度字符串
 * 按字节从高到低递归排序
 */
void msd_radix_sort_strings(char **arr, int lo, int hi,
                            int depth, int max_len)
{
    if (hi <= lo || depth >= max_len) return;

    // 小数组切换到插入排序
    if (hi - lo < 32) {
        insertion_sort_strings(arr, lo, hi, depth);
        return;
    }

    int count[258] = {0};  // 0: 字符串结束, 1-256: 字符值

    // 计数
    for (int i = lo; i <= hi; i++) {
        int c = (unsigned char)arr[i][depth];
        count[c + 2]++;
    }

    // 前缀和
    for (int i = 1; i < 258; i++) {
        count[i] += count[i - 1];
    }

    // 分配到辅助数组
    char **aux = malloc((hi - lo + 1) * sizeof(char *));
    for (int i = lo; i <= hi; i++) {
        int c = (unsigned char)arr[i][depth];
        aux[count[c + 1]++] = arr[i];
    }

    // 复制回原数组
    for (int i = lo; i <= hi; i++) {
        arr[i] = aux[i - lo];
    }
    free(aux);

    // 对每个桶递归
    for (int c = 0; c < 256; c++) {
        int sub_lo = lo + count[c];
        int sub_hi = lo + count[c + 1] - 1;
        if (sub_lo < sub_hi) {
            msd_radix_sort_strings(arr, sub_lo, sub_hi,
                                   depth + 1, max_len);
        }
    }
}

8.5 IP 地址排序

IPv4 地址本质是 32 位无符号整数，可以直接使用 LSD 基数排序。IPv6 是 128 位，可以按 4 个 32 位段分别处理，或用 16 轮按字节排序。对于附带额外数据的场景（如路由表项），建议使用间接排序：先排序键的索引数组，再按索引重排原数组，避免大结构体的散射写入开销。

九、完整实现

9.1 LSD 基数排序完整实现

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define RADIX_BITS  8
#define RADIX       (1 << RADIX_BITS)  // 256
#define MASK        (RADIX - 1)        // 0xFF

/*
 * LSD 基数排序完整实现
 *
 * 特点：
 *   - 基数 256，32 位整数 4 轮完成
 *   - 跳过全部相同的数字位（单桶优化）
 *   - 支持有符号整数（符号位翻转）
 *   - 使用指针交换避免不必要的复制
 *
 * 参数：
 *   arr  - 待排序数组
 *   n    - 数组长度
 *
 * 时间复杂度：O(d * n)，d = 4（32 位 / 8 位）
 * 空间复杂度：O(n)
 */
void lsd_radix_sort(int32_t *arr, int n)
{
    if (n <= 1) return;

    uint32_t *src = (uint32_t *)arr;
    uint32_t *dst = malloc(n * sizeof(uint32_t));
    if (!dst) return;

    // 预先统计所有轮次的直方图，只需一次遍历
    int hist[4][RADIX] = {{0}};
    for (int i = 0; i < n; i++) {
        uint32_t val = src[i];
        hist[0][ val        & MASK]++;
        hist[1][(val >>  8) & MASK]++;
        hist[2][(val >> 16) & MASK]++;
        hist[3][(val >> 24) & MASK]++;
    }

    for (int pass = 0; pass < 4; pass++) {
        int shift = pass * RADIX_BITS;

        // 单桶检测：如果某一位上所有元素都相同，跳过该轮
        int skip = 0;
        for (int i = 0; i < RADIX; i++) {
            if (hist[pass][i] == n) {
                skip = 1;
                break;
            }
        }
        if (skip) continue;

        // 将直方图转为前缀和（起始偏移量）
        int offsets[RADIX];
        int total = 0;
        for (int i = 0; i < RADIX; i++) {
            offsets[i] = total;
            total += hist[pass][i];
        }

        // 对于最高字节（pass==3），处理有符号整数
        if (pass == 3) {
            total = 0;
            // 负数先（0x80-0xFF）
            for (int i = 128; i < 256; i++) {
                offsets[i] = total;
                total += hist[3][i];
            }
            // 正数后（0x00-0x7F）
            for (int i = 0; i < 128; i++) {
                offsets[i] = total;
                total += hist[3][i];
            }
        }

        // 散射分配
        for (int i = 0; i < n; i++) {
            int digit = (src[i] >> shift) & MASK;
            dst[offsets[digit]++] = src[i];
        }

        // 交换 src 和 dst
        uint32_t *tmp = src;
        src = dst;
        dst = tmp;
    }

    // 确保结果在原数组中
    if (src != (uint32_t *)arr) {
        memcpy(arr, src, n * sizeof(int32_t));
        free(src);
    } else {
        free(dst);
    }
}

9.2 MSD 基数排序完整实现

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define MSD_RADIX      256
#define MSD_THRESHOLD  64   // 小数组切换到插入排序

/*
 * 插入排序：用于小数组
 */
static void insertion_sort_u32(uint32_t *arr, int n)
{
    for (int i = 1; i < n; i++) {
        uint32_t key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

/*
 * MSD 基数排序：递归核心
 *
 * 参数：
 *   arr   - 待排序子数组
 *   n     - 子数组长度
 *   shift - 当前处理的位偏移（从高到低：24, 16, 8, 0）
 */
static void msd_radix_sort_impl(uint32_t *arr, int n, int shift)
{
    if (n <= 1) return;

    // 小数组用插入排序
    if (n < MSD_THRESHOLD) {
        insertion_sort_u32(arr, n);
        return;
    }

    if (shift < 0) return;

    int count[MSD_RADIX + 1] = {0};

    // 计数
    for (int i = 0; i < n; i++) {
        count[((arr[i] >> shift) & 0xFF) + 1]++;
    }

    // 前缀和
    for (int i = 1; i <= MSD_RADIX; i++) {
        count[i] += count[i - 1];
    }

    // 分配到辅助数组
    uint32_t *aux = malloc(n * sizeof(uint32_t));
    if (!aux) return;  // 内存分配失败时退出

    for (int i = 0; i < n; i++) {
        int digit = (arr[i] >> shift) & 0xFF;
        aux[count[digit]++] = arr[i];
    }

    memcpy(arr, aux, n * sizeof(uint32_t));
    free(aux);

    // 对每个桶递归排序
    int start = 0;
    for (int d = 0; d < MSD_RADIX; d++) {
        int end = count[d];
        int bucket_size = end - start;
        if (bucket_size > 1) {
            msd_radix_sort_impl(arr + start, bucket_size, shift - 8);
        }
        start = end;
    }
}

/*
 * MSD 基数排序：入口函数
 * 支持 32 位有符号整数
 */
void msd_radix_sort(int32_t *arr, int n)
{
    if (n <= 1) return;

    uint32_t *data = (uint32_t *)arr;

    // 翻转符号位：使负数按位值排在正数前面
    for (int i = 0; i < n; i++) {
        data[i] ^= 0x80000000u;
    }

    msd_radix_sort_impl(data, n, 24);

    // 恢复符号位
    for (int i = 0; i < n; i++) {
        data[i] ^= 0x80000000u;
    }
}

9.3 ska_sort 风格的就地基数排序

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define SKA_RADIX      256
#define SKA_THRESHOLD  128

/*
 * 插入排序：用于小数组
 */
static void ska_insertion_sort(uint32_t *arr, int n)
{
    for (int i = 1; i < n; i++) {
        uint32_t key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

/*
 * ska_sort 风格的就地 MSD 基数排序
 *
 * 核心优化：
 *   1. 就地分区，不需要辅助数组
 *   2. 循环置换（cycle sort）风格的元素交换
 *   3. 小数组回退到插入排序
 *   4. 单桶跳过优化
 *
 * 参数：
 *   arr   - 待排序子数组
 *   n     - 子数组长度
 *   shift - 当前处理的位偏移
 */
static void ska_sort_impl(uint32_t *arr, int n, int shift)
{
    if (n <= 1 || shift < 0) return;

    if (n < SKA_THRESHOLD) {
        ska_insertion_sort(arr, n);
        return;
    }

    // 计数
    int count[SKA_RADIX] = {0};
    for (int i = 0; i < n; i++) {
        count[(arr[i] >> shift) & 0xFF]++;
    }

    // 检测单桶：所有元素在当前位相同
    int num_buckets = 0;
    for (int i = 0; i < SKA_RADIX; i++) {
        if (count[i] > 0) num_buckets++;
    }
    if (num_buckets == 1) {
        ska_sort_impl(arr, n, shift - 8);
        return;
    }

    // 计算桶边界
    int starts[SKA_RADIX];
    int ends[SKA_RADIX];
    int offsets[SKA_RADIX];
    int pos = 0;
    for (int i = 0; i < SKA_RADIX; i++) {
        starts[i] = pos;
        offsets[i] = pos;
        pos += count[i];
        ends[i] = pos;
    }

    // 就地循环排列
    for (int bucket = 0; bucket < SKA_RADIX; bucket++) {
        while (offsets[bucket] < ends[bucket]) {
            uint32_t elem = arr[offsets[bucket]];
            int target = (elem >> shift) & 0xFF;

            if (target == bucket) {
                offsets[bucket]++;
                continue;
            }

            // 循环交换
            do {
                uint32_t tmp = arr[offsets[target]];
                arr[offsets[target]] = elem;
                offsets[target]++;
                elem = tmp;
                target = (elem >> shift) & 0xFF;
            } while (target != bucket);

            arr[offsets[bucket]] = elem;
            offsets[bucket]++;
        }
    }

    // 对每个非空桶递归
    for (int i = 0; i < SKA_RADIX; i++) {
        int bucket_size = ends[i] - starts[i];
        if (bucket_size > 1) {
            ska_sort_impl(arr + starts[i], bucket_size, shift - 8);
        }
    }
}

/*
 * ska_sort 入口：32 位有符号整数
 */
void ska_sort(int32_t *arr, int n)
{
    if (n <= 1) return;

    uint32_t *data = (uint32_t *)arr;

    // 翻转符号位
    for (int i = 0; i < n; i++) {
        data[i] ^= 0x80000000u;
    }

    ska_sort_impl(data, n, 24);

    // 恢复符号位
    for (int i = 0; i < n; i++) {
        data[i] ^= 0x80000000u;
    }
}

9.4 测试程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>

void lsd_radix_sort(int32_t *arr, int n);
void msd_radix_sort(int32_t *arr, int n);
void ska_sort(int32_t *arr, int n);

static int cmp_int32(const void *a, const void *b)
{
    int32_t x = *(const int32_t *)a, y = *(const int32_t *)b;
    return (x > y) - (x < y);
}

static void verify(int32_t *arr, int n)
{
    for (int i = 1; i < n; i++) assert(arr[i - 1] <= arr[i]);
}

static void bench(const char *name, void (*fn)(int32_t *, int),
                  int32_t *orig, int n)
{
    int32_t *arr = malloc(n * sizeof(int32_t));
    memcpy(arr, orig, n * sizeof(int32_t));
    clock_t t0 = clock();
    fn(arr, n);
    double ms = (double)(clock() - t0) / CLOCKS_PER_SEC * 1000;
    verify(arr, n);
    printf("  %-20s: %.2f ms\n", name, ms);
    free(arr);
}

int main(void)
{
    srand(42);
    int sizes[] = {10000, 100000, 1000000};
    for (int s = 0; s < 3; s++) {
        int n = sizes[s];
        int32_t *data = malloc(n * sizeof(int32_t));
        for (int i = 0; i < n; i++)
            data[i] = (int32_t)rand() - RAND_MAX / 2;

        printf("n = %d:\n", n);
        bench("LSD Radix Sort", lsd_radix_sort, data, n);
        bench("MSD Radix Sort", msd_radix_sort, data, n);
        bench("ska_sort",       ska_sort,       data, n);

        int32_t *q = malloc(n * sizeof(int32_t));
        memcpy(q, data, n * sizeof(int32_t));
        clock_t t0 = clock();
        qsort(q, n, sizeof(int32_t), cmp_int32);
        printf("  %-20s: %.2f ms\n", "qsort (baseline)",
               (double)(clock() - t0) / CLOCKS_PER_SEC * 1000);
        free(q);
        free(data);
        printf("\n");
    }
    return 0;
}

十、与 pdqsort / std::sort 的性能对比

10.1 理论复杂度对比

注：d = 位数/基数位数，k = 基数大小。pdqsort 的最坏情况通过 heapsort 回退保证。

10.2 跨数据类型的实际性能

以下是不同数据类型和数据规模下的性能对比（基于典型 x86-64 平台的经验数据）。相对性能用 pdqsort 作为基准 1.0x：

32 位整数排序（均匀随机）：

注：< 1.0x 表示比 pdqsort 快。基数排序在 n > 10K 时开始显现优势。

64 位整数排序（均匀随机）：

64 位整数需要 8 轮（LSD），优势减小。

字符串排序（随机 ASCII，平均长度 16）：

MSD 基数排序在字符串上也能胜出，但优势不如整数场景明显。

struct 排序（按 32 位整数键）：

关键发现：当元素体积增大时，基数排序的优势迅速消失。散射写入大元素比交换两个指针（间接排序）贵得多。对于大元素，应该先提取键做间接排序。

10.3 分布对性能的影响

数据分布对基数排序和比较排序的影响非常不同：

均匀随机分布：
  基数排序：稳定的 O(dn)，与分布无关
  pdqsort：平均 O(n log n)，分区质量好

几乎有序：
  基数排序：仍然是 O(dn)，无法利用已有顺序
  pdqsort：接近 O(n)，插入排序回退非常快

少量唯一值（如 [0, 1, 2] 重复）：
  基数排序：可能只需 1-2 轮（高位全部相同，可跳过）
  pdqsort：Dutch National Flag 三路分区，接近 O(n)

逆序：
  基数排序：O(dn)，与正序一样
  pdqsort：检测后反转，O(n)

pdqsort 这类自适应排序算法在非随机数据上有巨大优势。基数排序的「数据无关性」既是优点（可预测），也是缺点（无法利用结构）。

十一、工程陷阱

在实际使用基数排序时，有许多容易被忽视的细节问题。以下是我在实践中遇到或观察到的常见陷阱：

11.1 典型 Bug 示例

以下是一个常见的 bug——LSD 最后一轮结果可能在辅助数组中：

// 错误版本
void buggy_radix_sort(uint32_t *arr, int n)
{
    uint32_t *aux = malloc(n * sizeof(uint32_t));

    for (int pass = 0; pass < 4; pass++) {
        // ... 排序从 arr 到 aux ...

        // BUG: 每轮都把 aux 复制回 arr
        // 这浪费了一半的时间！
        memcpy(arr, aux, n * sizeof(uint32_t));
    }

    free(aux);
}

// 正确版本：使用 ping-pong buffer
void correct_radix_sort(uint32_t *arr, int n)
{
    uint32_t *buf = malloc(n * sizeof(uint32_t));
    uint32_t *src = arr;
    uint32_t *dst = buf;

    for (int pass = 0; pass < 4; pass++) {
        // ... 排序从 src 到 dst ...

        // 交换 src 和 dst
        uint32_t *tmp = src;
        src = dst;
        dst = tmp;
    }

    // 4 轮（偶数次交换），src == arr，结果正好在原数组
    // 如果是奇数轮，需要 memcpy
    if (src != arr) {
        memcpy(arr, src, n * sizeof(uint32_t));
    }

    free(buf);
}

11.2 避免过度优化

我见过一些工程师为了追求极致性能，对基数排序做了过度优化：

1. 使用 AVX-512 指令做直方图计数——代码复杂度增加 10 倍，性能提升不到 5%。
2. 手写内存池避免 malloc——对于一次性排序，malloc 的开销可以忽略。
3. 使用 16 位基数减少轮数——计数数组从 1 KB 膨胀到 256 KB，缓存反而更差。

优化应该从性能分析出发，而不是从直觉出发。在我的经验中，基数排序最大的性能杀手是缓存未命中，而不是指令数量。

十二、总结与思考

12.1 何时选择基数排序

选择基数排序的判断框架：

问题 1：键是否是固定长度的整数或定长字符串？
  否 -> 使用比较排序（pdqsort / timsort）
  是 -> 继续

问题 2：n 是否足够大（> 10K）使基数排序的常数因子被摊销？
  否 -> 使用比较排序
  是 -> 继续

问题 3：元素大小是否较小（<= 8 字节）或可以使用间接排序？
  否 -> 使用比较排序（大元素的散射写入太贵）
  是 -> 继续

问题 4：是否需要稳定排序？
  是 -> LSD 基数排序
  否 -> ska_sort / American Flag Sort

问题 5：数据是否可能已经部分有序？
  是 -> pdqsort 可能更快（自适应性）
  否 -> 基数排序

12.2 基数排序在算法史中的位置

基数排序的历史比电子计算机还长。Herman Hollerith 在 1890 年的美国人口普查中就使用了基于打孔卡片的基数排序机。在早期大型机时代，基数排序因为避免了昂贵的比较操作而广泛使用。

随着 CPU 缓存层级的复杂化和比较排序算法的不断优化（从快速排序到 introsort 再到 pdqsort），基数排序在通用场景中的地位被逐渐取代。但在特定场景——大规模整数排序、网络数据包分类、数据库列存储——它仍然是不可替代的。

12.3 个人观点

我认为基数排序的价值不在于它是「最快的排序算法」（它在很多场景下不是），而在于它揭示了一个深刻的算法设计原则：改变问题的抽象层次，可以绕过看似不可逾越的理论限制。

O(n log n) 的下界是比较模型的下界，不是排序本身的下界。当你能直接访问键的内部结构时，就打开了一个新的设计空间。这个思路在其他领域也反复出现：

• 哈希表绕过了比较搜索的 O(log n) 下界。
• 布隆过滤器用概率方法绕过了精确集合成员测试的空间下界。
• 量子算法用量子并行绕过了经典计算的查询复杂度下界。

每一次看似打破规则的突破，实际上都是找到了一个更合适的计算模型。理解这一点，比记住任何具体的排序算法都重要。

另一个值得深思的点是：理论最优不等于工程最优。基数排序在 RAM 模型下的 O(n) 看起来完美，但在真实的内存层级面前，缓存未命中的常数因子可以让「O(n)」比「O(n log n)」更慢。这提醒我们，分析算法不能只看大 O，还要看它背后的假设是否符合实际硬件。

最终，选择排序算法应该是一个工程决策：分析数据特征，测量实际性能，然后选择最适合当前场景的方案。基数排序是工具箱中的一把利器，但不是万能钥匙。

参考文献

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 8: Sorting in Linear Time.
2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. Section 5.2.5: Sorting by Distribution.
3. McIlroy, P. M., Bostic, K., & McIlroy, M. D. (1993). Engineering Radix Sort. Computing Systems, 6(1), 5-27.
4. Skarupke, M. (2016). ska_sort: A Practical Implementation of Ska Sort. https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
5. Wassenberg, J., & Sanders, P. (2011). Engineering a Multi-core Radix Sort. Euro-Par 2011 Parallel Processing, 160-169.
6. Obeya, O., Kahssay, E., Fan, E., & Shun, J. (2019). Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. SPAA 2019.
7. Peters, O. R. L. (2021). pdqsort: Pattern-Defeating Quicksort. https://github.com/orlp/pdqsort
8. LaMarca, A., & Ladner, R. E. (1999). The Influence of Caches on the Performance of Sorting. Journal of Algorithms, 31(1), 66-104.
9. Satish, N., Harris, M., & Garland, M. (2009). Designing Efficient Sorting Algorithms for Manycore GPUs. IEEE IPDPS 2009.
10. Polychroniou, O., Raghavan, A., & Ross, K. A. (2015). Rethinking SIMD Vectorization for In-Memory Databases. SIGMOD 2015.

算法系列导航：上一篇：pdqsort | 下一篇：外部排序

相关阅读：SIMD 算法设计模式 | 排序基准测试