基数排序

定义

基数排序（Radix Sort）是一种 非比较 排序算法：将整数按 数位（digit） 拆分，从 低位到高位（LSD）依次做稳定排序，最终得到有序序列。

每一轮数位排序本质是键值范围很小的 计数排序：本实现基数 BASE = 10，每轮对当前位（个位、十位、百位……）在 $[0,9]$ 上计数、做前缀和，再 逆序放置。子过程稳定，整体才 稳定。

适用于 非负整数 且位数 $d$ 不太大的场景。设 $n$ 为元素个数、$k$ 为最大值的位数（或基数相关参数），时间复杂度为 $O(n\times k)$。

特性：平均 $O(n\times k)$ · 最好 $O(n\times k)$ · 最坏 $O(n\times k)$ · 空间 $O(n+k)$ · 非原地 · 稳定

过程

工作原理：将每个数按十进制拆成若干 数位，从 个位到高位（LSD）逐轮排序。每轮只看 当前位，按 0–9 分入对应桶，再按桶序依次取出——桶内保持放入顺序，即 稳定 收集。

1. 确定轮数：看最大值有几位，就处理几位（个位、十位、百位……）。
2. 按位分桶：取当前位，元素落入 0–9 号桶；不足位的数视为高位补 0（如 5 的十位为 0）。
3. 按序收集：从 0 号桶到 9 号桶依次取出，桶内从上到下保持原序，写回序列。
4. 重复：处理下一位，直至最高位排完。

动图对 [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] 执行两轮（最大值 50 为两位）。下方 0–9 号桶对应当前位的值；元素按当前位落入桶中，再按桶序收集。

第一轮：按个位

桶	0	1	2	3	4	5	6	7	8	9
分桶	50		2	3	44, 4	5, 15	36, 26, 46	47, 27	38, 48	19

按桶序收集：[50, 2, 3, 44, 4, 5, 15, 36, 26, 46, 47, 27, 38, 48, 19]。44 与 4 个位同为 4，输入时 44 在前，收集后仍在前，体现稳定。

第二轮：按十位

桶	0	1	2	3	4	5	6	7	8	9
分桶	2, 3, 4, 5	15, 19	26, 27	36, 38	44, 46, 47, 48	50

按桶序收集：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]，全部有序。个位数视为十位 0，故 2、3、4、5 落入 0 号桶。

为什么是低位优先（LSD）

第一轮按个位排完，结果看起来「很乱」——50 到了最前。但 LSD 的关键在于：当前位相同时，保留上一轮已排好的相对顺序。

轮次	结果	此时保证了什么
个位	[50, 2, 3, 44, 4, 5, 15, 36, 26, 46, 47, 27, 38, 48, 19]	个位有序；同桶内顺序与输入一致
十位	[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]	十位相同时保留个位结果；十位不同则直接分开 → 全序正确

以 26 与 46 为例：个位轮同在 6 号桶，输入时 26 在前；十位轮两者十位均为 2，落入同一桶，顺序不变。36 与 38 十位同为 3，个位轮已是 36 → 38，十位轮顺序仍不变。

高位不同的数不必等低位「传上来」——44 与 46 十位同为 4，个位轮 44 已在 46 前，十位轮同桶顺序保持；50 十位为 5，单独成桶，自然落到末尾。

若改成 高位优先 且仍对全数组逐轮分桶，最后一轮按个位排时 只看个位，会把前面排好的大小关系打散。以 [170, 45, 75, 90] 为例：百位、十位轮结束后，个位轮会得到 [170, 90, 45, 75]——170 只因个位为 0 被挪到最前。要从高位开始，需要 MSD 分桶递归（按位分桶、桶内再排下一位），那是另一套流程。

每轮分桶的底层实现通常用 计数排序（计数 → 前缀和 → 从右向左放置），详见「代码实现」。

性质

稳定性

基数排序是 稳定 排序算法，但稳定性 不是 自动成立的——它依赖每轮子过程 前缀和与遍历方向配对正确。

本实现用 结束下标 + 逆序放置：前缀和给出各 digit 的右边界，从右向左扫描时，相同 digit 中靠后的元素先占位，相对顺序与输入一致，低位轮的结果才能带入高位轮。

若某轮子过程不稳定（下标语义与遍历方向不配，或桶内使用快排），整体也不再稳定。

时间复杂度

情况	复杂度	说明
最好	$O(n\times k)$	共 $k$ 轮，每轮计数排序 $O(n+\text{BASE})$
最坏	$O(n\times k)$	与输入分布无关
平均	$O(n\times k)$	同上

$k$ 为最大值的位数；BASE 为基数（本实现为 $10$），每轮额外扫 $O(\text{BASE})$ 个桶。

空间复杂度

$O(n+\text{BASE})$。需要长度 $n$ 的辅助数组 output；每轮计数数组大小为 BASE。按惯例归入 非原地。

代码实现

源码: https://github.com/lllllan02/ciu/tree/master/code/radix-sort

基础写法

本仓库实现。LSD 基数排序，BASE = 10，每轮对当前位做稳定计数排序：

#define BASE 10
 
static int bucket_index(int value, int exp) {
    return (value / exp) % BASE;
}
 
void radix_sort(int* arr, int len) {
    if (len <= 1) return;
 
    int max = arr[0];
    for (int i = 1; i < len; i++) {
        if (arr[i] > max) max = arr[i];
    }
 
    int exp = 1;
    int* output = malloc(len * sizeof(int));
    if (!output) return;
 
    while (max / exp > 0) {
        int buckets[BASE] = {0};
 
        for (int i = 0; i < len; i++) {
            buckets[bucket_index(arr[i], exp)]++;
        }
 
        for (int i = 1; i < BASE; i++) {
            buckets[i] += buckets[i - 1];
        }
 
        for (int i = len - 1; i >= 0; i--) {
            int index = bucket_index(arr[i], exp);
            int pos = --buckets[index];
            output[pos] = arr[i];
        }
 
        for (int i = 0; i < len; i++) {
            arr[i] = output[i];
        }
 
        exp *= BASE;
    }
 
    free(output);
}

参考阅读

• OI Wiki - 基数排序 (2026-06-11)
• 菜鸟教程 - 基数排序 (2026-06-11)
• 基数排序
• 基数排序（视频）
• 基数排序, 计数排序 (线性时间内)（视频）
• CS 61B 2014-04-21：基数排序（视频）
• 线性时间内的排序（视频）
• Radix sort in 3 minutes (video)