基数排序详解：非比较排序的分桶原理与工程实战

我在带算法集训的时候，排序专题习惯分成两个阶段：前段日子把比较排序挨个啃完，第九天刚把快排和归并的递归栈捋顺，到第十天聊基数排序，学生普遍会愣一下——这不是“按大小排队”吗，跟“位数”有什么关系？

基数排序的意义就在这：它是排序题里少见的“非比较型排序”，不靠两两之间比大小，而是靠“分桶”和“次数”直接把数据摆到正确位置。集训安排到第十天讲它，不是因为它难，而是因为它是检验学生能不能跳出“比较思维”的最好试金石。这篇内容适合正在系统学排序、准备算法面试，或者刷了不少排序题但总觉得“快排就是终极答案”的人阅读。我会从原理、手推案例、代码实现到负数处理这些实战坑全部拆一遍，照着走一遍基本就能自己写出来了。

1. 为什么排序集训要安排一次基数排序

1.1 比较型排序的天花板：快排、归并、堆排绕不过去的坎

先想一个问题：为什么我们前九天学的快排、归并、堆排，再优化下限也就是 O(n log n)？因为只要核心操作是“两个数比大小”，那一次比较最多只能获得两三个信息位。就好像一场淘汰赛，每一轮只能淘汰一半人，信息获取是二进制的。这在信息论里早就被证明了：所有基于比较的排序，平均情况不可能低于 n log n 次比较。

那有没有可能绕过比较，直接靠一把“尺子”把每个数字量到它该去的位置上？有，桶排序的思路就是干这个的。但桶排序有个硬伤：如果数值范围很大，比如发动 10 万个整数，范围从 1 到 1 亿，直接开 1 亿个桶纯属灾难。基数排序恰恰是桶排序的改良版——我不直接按数值大小开桶，而是按“位数”来处理，一位一位地把数抖落明白。

这是理解基数排序的第一个关键点：它把一个“范围很大的分布”拆成“很多轮范围很小的分布”，每轮只关注一位数字，然后串起来。

1.2 集训第十天的教学逻辑：从“比较”到“分配”

前九天把比较排序学完，学生对排序复杂度已经形成了“跟数量有关”的直觉：100 万个数要排序，快排大概跑个两三秒，归并差不多，堆排稍慢一点。他们很难想象存在一种排序，耗时跟“数的位数”更相关，而不是跟“数之间怎么比”更相关。

第 10 天安排基数排序，正好接住这个好奇。我给学生的引导问题很有意思：“如果待排序数组里最大数是 9999，最小数是 1，你会怎么排？”有人会说“先排千位”，有人会说“分四组”，但很少有人想到从个位开始向高位移。这也是接下来要重点讲的思维反转。

基数排序和快排、归并还有个不同：快排、归并靠分治，递归或显式栈；基数排序基本是循环，迭代轮数就是最大数的位数。这意味它的行为和比较排序完全不同，非常适合被拿来做“复杂度分析训练”，因为你能很直观地看出 d、n、k 三个参数是怎么互相牵制的。

1.3 基数排序适合的典型场景

先明确适用范围，不然容易踩坑。基数排序适合：数据量很大（几十万以上）、数据是整数或可拆成整数位的结构（比如固定长度字符串），并且数值范围相对位数不会太离谱。

实际开发中最常见的例子是：对几十万个 ID、学号、手机号后四位做排序。你要用快排也一样排，但用基数排序实现也不难，而且没有比较的开销，纯循环和数组访问，对某些数据分布反而更稳定。

另外一个经典场景在数据库和外部排序里：当数据量大到必须分批读写磁盘时，基数排序的分桶特性有利于“一轮走完一遍数据再收集”，比快排的递归访问模式对缓存和磁盘更友好。这个特性在算法竞赛里也许体现得不够直接，但在工程大件任务里非常有用。

2. 基数排序的核心思想与设计逻辑

2.1 从“比较大小”到“按位分桶”

所谓基数，简单说就是“每一轮分几个桶”。如果按十进制处理数字，那每一轮分 10 个桶，因为每一位数字只可能是 0 到 9；如果按二进制位处理，每一轮分 2 个桶；如果一次处理一个字节，每一轮分 256 个桶。

拿经典例子数组 [170, 45, 75, 90, 802, 24, 2, 66] 来说，第一轮看“个位”，个位是 0 的放 0 号桶，是 2 的放 2 号桶，是 4 的放 4 号桶，是 5 的放 5 号桶，是 6 的放 6 号桶。然后再按桶的顺序收集起来，第一轮结束以后，数组里所有元素已经满足“个位有序”。第二轮看“十位”，第三轮看“百位”，三轮结束以后整个数组就有序了。

聪明的人会问：所有元素都先按个位排好了，第二轮按十位排，会不会把个位的顺序打乱？答案是不会，前提是你每一轮必须用稳定的方式分桶。这个稍后详细说。先接受一个结论：只要每轮稳定，低位的次序会在高位的处理过程中被保留，最后一轮收口就全对了。

2.2 LSD 与 MSD：两条路线的取舍

基数排序有两种主流路线：

• LSD（Least Significant Digit）：从最低位（个位）开始向最高位处理。排整数时最常用，实现简单，代码好写，适合编程教学和竞赛。
• MSD（Most Significant Digit）：从最高位向最低位处理。优点是可以配合递归、甚至配合插入排序做“小区间优化”，通常在字符串排序里更实用，比如按字典序排单词，首字母优先级最高。

集训里我会先讲 LSD，因为逻辑闭环直观。但面试中如果被问到“怎么排序 10 万个长度不超过 10 的字符串”，很多人的第一反应也是从首字母开始分 26 类，这就是 MSD 的直觉。两条路线没有哪个绝对更好，取决于应用场景：LSD 代码短，适合数据均匀、位数一致的整数；MSD 能早早在高位上区分出区间，适合字符串这类“前面几位决定最终顺序”的数据。

2.3 稳定性是基数排序的命根子：为什么内层必须用稳定排序

很多第一次接触基数排序的人，会天真地用普通桶排序做内层，结果排完一位再按下一位时，整个数组乱掉。原因就是桶操作不稳定，把之前排好的低位次序破坏了。

举个例子：[33, 32, 11]，第一轮按个位分桶，个位为 2 的只有 32，个位为 1 的只有 11，个位为 3 的有 33，收集后是 [32, 11, 33]。第二轮按十位分桶，十位为 3 的有 33 和 32，十位为 1 的有 11。如果这个“十位为 3”的桶里你不保持原本顺序，收集后可能是 [11, 33, 32]，那就错了。反过来，如果稳定地保持 [33, 32] 的顺序，结果就是 [11, 33, 32]，正确。

所以算法社区里强调：基数排序内部最稳的帮手是计数排序。计数排序天然适合做稳定分桶：先数清每个数字出现的次数，再转成“每个桶下一个元素应该放到的起点位置”，最后从后往前填到输出数组，把原位次保留下来。这既高效又稳定，是基数排序的标准配置。

3. 基数排序实操全程拆解

3.1 经典数据手推：170, 45, 75, 90, 802, 24, 2, 66

我用集训课上必推的一组数据带你走一遍，自己最好拿草稿纸跟着写：

初始数组：[170, 45, 75, 90, 802, 24, 2, 66]

第一轮，按个位分桶：

• 个位 0：170、90
• 个位 2：802、2
• 个位 4：24
• 个位 5：45、75
• 个位 6：66

收集后得到：[170, 90, 802, 2, 24, 45, 75, 66]。

注意这个序列里个位已经升序了：0, 0, 2, 2, 4, 5, 5, 6。

第二轮，按十位分桶，把上面的数组依次看：

• 170 的十位是 7，90 的十位是 9，802 的十位是 0，2 的十位是 0（严格说是没有十位，取 0），24 的十位是 2，45 的十位是 4，75 的十位是 7，66 的十位是 6。

分桶后：

• 十位 0：802、2
• 十位 2：24
• 十位 4：45
• 十位 6：66
• 十位 7：170、75
• 十位 9：90

收集：[802, 2, 24, 45, 66, 170, 75, 90]。

第三轮，按百位分桶：

• 802 百位 8，2 百位 0，24 百位 0，45 百位 0，66 百位 0，170 百位 1，75 百位 0，90 百位 0。

分桶：

• 百位 0：2、24、45、66、75、90
• 百位 1：170
• 百位 8：802

收集：[2, 24, 45, 66, 75, 90, 170, 802]。排好了。

每一轮“收集”默认按桶编号从小到大，桶内按投入顺序保持，稳定性就是从这里保住的。

3.2 代码实现：Python 版与 C++ 版

先给 Python 版本。这里用计数排序做稳定内层，可以在 leetcode 或本地直接跑：

def counting_sort_for_radix(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 # 十进制，10个桶 for num in arr: index = (num // exp) % 10 count[index] += 1 # 累加，得到每个桶的最后一个元素的最终位置 for i in range(1, 10): count[i] += count[i - 1] # 从后往前填充，保证稳定性 for i in range(n - 1, -1, -1): index = (arr[i] // exp) % 10 output[count[index] - 1] = arr[i] count[index] -= 1 for i in range(n): arr[i] = output[i] def radix_sort(arr): if not arr: return arr max_val = max(arr) exp = 1 while max_val // exp > 0: counting_sort_for_radix(arr, exp) exp *= 10 return arr

再看 C++ 版本，思路一致。C++ 里要注意函数不要修改原数组的临时状态太多，保持代码清晰：

#include <vector> #include <algorithm> using namespace std; void countingSortForRadix(vector<int>& arr, int exp) { int n = arr.size(); vector<int> output(n); vector<int> count(10, 0); for (int num : arr) { int idx = (num / exp) % 10; count[idx]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { int idx = (arr[i] / exp) % 10; output[count[idx] - 1] = arr[i]; count[idx]--; } for (int i = 0; i < n; i++) { arr[i] = output[i]; } } void radixSort(vector<int>& arr) { if (arr.empty()) return; int maxVal = *max_element(arr.begin(), arr.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) { countingSortForRadix(arr, exp); } }

这里最值得讲的是倒序填充那一段。为什么从后往前？因为 count 数组累加后，count[digit] 表示“digit 这个桶里最后一个元素应该落在 output 的哪个下标”。从后往前遍历原数组，同一个 digit 桶内后访问到的元素会被放到靠前的位置，最终等于保住了原数组的相对顺序。这个细节我见过很多初学者卡住，一旦想通，稳定性的实现就彻底掌握了。

3.3 复杂度推导与参数选择：d、n、k 之间的关系

设数组长度 n，最大数位数为 d，基数为 k，也就是桶的数量。每一轮遍历一遍数组做分类，复杂度 O(n)，再遍历一遍 count 数组做前缀和，复杂度 O(k)。总共做 d 轮，所以总时间复杂度是：

O(d × (n + k))

空间方面，需要输出数组 O(n)，以及计数数组 O(k)，总空间 O(n + k)。

这个公式很有意思：当 d、k 都是常数级时，基数排序就是线性复杂度。比如做 32 位整数排序，如果取基数 256，那么 d = 4，k = 256，无论 n 多大，都只需要 4 轮处理。在 n 达到几百万时，这个效率确实能和快排掰手腕，甚至更强。

但要注意，它的内存访问方式不像快排那样局部化，频繁访问 count 数组会带来缓存压力，所以“理论线性”不等于“现实总最快”。这也是为什么我在集训里强调，别盲目叫它“最快的排序”，要看场景。

3.4 工程优化：用 2 的幂做基数、按字节处理

教科书喜欢用十进制，因为数学上直观。实际写代码，我建议你尝试用基数 256，也就是一次处理一个字节。原因很简单：对整数取十进制位要做/10和%10，这两个操作在 CPU 上是除法运算，相对慢；而取字节只需要x & 0xFF和右移x >> (8 * byteIndex)，全部是位运算，快得多。

以 32 位整数为例：

for (int byte = 0; byte < 4; byte++) { int shift = byte * 8; int idx = (x >> shift) & 0xFF; }

这样每一轮桶数为 256，数组长度 n 很大时，空间和速度都能接受。我在工程里帮人优化过“大量内网设备 ID 排序”的需求，换成字节型基数排序后，比原先用 std::sort 快了不少，原因就是避免了比较函数调用开销，也减少了除法运算。

4. 实战中的坑与排查技巧

4.1 负数排序的三种解法

最直接的问题：如果数组里有负数，上面代码会直接打回原形。因为%10在 C++ 里对负数结果可能是负的，比如-3 % 10 = -3，下标直接越界。

有三种常见解法：

1. 偏移法：找到最小值 minVal，把所有数先减去 minVal，转成非负数；排完序再统一加回来。比如 [-5, 3, -2]，minVal = -5，转换后为 [0, 8, 3]，排序得到 [0, 3, 8]，再减去 -5 得到 [-5, -2, 3]。这个方法最简单，但要求数据范围不太大，否则偏移量太大会浪费。

2. 正负分段法：把负数取绝对值排序，然后把正数部分和负数部分合并，负数部分要逆序排放。

3. 补码思路：对整数按二进制位处理，符号位本身就参与排序，不过实现起来更绕，一般面试只要说得出思路就行。

实战中我推荐偏移法，最少改动原代码。不过要注意偏移量本身可能较大，排序过程仍基于处理后的非负数，整体复杂度不变。

4.2 基数选择：10、256 还是 2

三种选择的本质是让 d 和 k 互相权衡：

基数越大，每轮分桶更粗，轮数越少，但 count 数组和内存开销越大；基数太小，比如 2，会导致轮数爆炸。工程上取 256 是性能和使用复杂度的平衡点，也便于用位运算。

4.3 内存开销与大数据场景取舍

当你处理千万级数据时，基数排序每轮都要复制一次整个数组到 output，千万整数就是几 MB 到几十 MB 的内存消耗，比快排的递归栈开销要高不少。如果内存紧张，基数排序的优势会被冲淡。另外，对布尔类型或极窄范围的数组，开 256 个桶纯属浪费，直接计数排序就够了，不用绕多层。

这里我踩过一个坑：曾经对一个 5000 万整数的数组做排序，选用基数 256，内存是够的，但外层循环每轮都会触碰整个数组，后来发现主要瓶颈反而是内存带宽。之后改成减少无谓复制，比如使用两个数组交替作为输入输出，而不是每轮新建一个数组，才把时间压下来。

4.4 常见问题速查表

5. 从面试到竞赛：基数排序的延伸用法

5.1 典型题目与变形

除了最基础的整数排序，面试里常见三种变形：

• 字符串排序：对固定长度字符串排序，可以按字符的 ASCII 码从末位到首位的 LSD 处理，或者从首到尾的 MSD 处理。
• 在 O(n) 内排序范围有限的整数：比如所有数都在 0 到 1000 之间，直接用计数排序就行，没必要上基数。
• 求最大间距：经典 LeetCode 164 题“Maximum Gap”，空桶法解决，本质上和桶排序、基数排序的“按范围分桶”思想一脉相承。会遇到抽象成“把数映射到桶分组，再检查桶间距离”的思维，和基数排序的分桶是同一套原理。

这类题在集训里做起来很有意思，因为你会发现“分桶”不光是排序手段，还是一种把大问题拆小的大局观。

5.2 和其他算法的联动：字符串、哈希、图算法里的“稳定分桶”

许多人以为基数排序只能对整数用，实际它的“稳定分桶”思想可以延伸到不少常见场景。

做字符串子串查找时，有人提到 KMP 算法，但基数排序可以作为后缀数组构建中的一个预处理步骤，对后缀按首字符、次字符轮番排序，获得字典序基础顺序。这和单纯的 KMP 字符串匹配是两个层次的问题。

另外，做大规模去重时，把数据先转成哈希值，再对哈希值做基数排序，能快速分块、判重，这种思路比直接建哈希表要省内存。再比如图算法中需要按键值排序某些边、顶点标号时，基数排序也能帮你在线性时间内组织好结构。

所以不要只把它看成一个“整数排序工具”，它的核心价值在于“稳定地把元素按某一位键值分到有序桶里”，很多问题套上这个壳就能用。

5.3 什么时候不该用基数排序

再好的工具也有边界。基数排序不擅长的场景：

• 数据量很小（几百个元素）：常数开销可能抵消算法优势，直接用插入排序或库排序就够了。
• 浮点数排序且要求高精度：直接把 float 按字节位拆出来排，符号位、指数位、尾数位的映射关系复杂，容易出错，不如 std::sort 稳。
• 非整数结构但没法抽出“位”：比如对象数组依据任意 compare 函数排序，基数排序不能直接用。
• 对内存极其敏感的环境：每轮复制大数组的消耗可能无法接受。

用实战收个尾

集训第十天快结束时，我会给学生留个小实验：生成 100 万个 0 到 100 万的随机整数，分别用快排、归并、基数排序跑一遍，然后记录时间。实验做下来，基数排序往往跟快排有来有回，但换到数据集中在某些区间时，基数排序的优势会更明显。这个实验本身比我反复讲原理更有说服力。

我自己在实际写排序代码时，有个习惯：如果明确知道数据范围不大、都是整数，我会偷懒用基数排序，因为它几乎没有递归深度风险，也不会出现快排最坏情况退化到 O(n²) 的隐患。但凡是排序对象包含浮点、负数、大范围长尾分布，我还是老老实实回到 std::sort 的怀抱。技术选型这事，没有银弹，只有“当前数据适不适合”的判断。

最后分享一个小技巧：如果你用 Python 写，可以只改几行就把上面代码改成支持任意基数——把 count 数组长度从 10 换成 radix，并把取位的index = (num // exp) % 10改成index = (num // exp) % radix，这样代码可复用性会好很多。往后再遇到“基数 2 的进制数排序”之类的题目，你只需要改一个参数，其余逻辑纹丝不动。