我在带算法集训的时候排序专题习惯分成两个阶段前段日子把比较排序挨个啃完第九天刚把快排和归并的递归栈捋顺到第十天聊基数排序学生普遍会愣一下——这不是“按大小排队”吗跟“位数”有什么关系基数排序的意义就在这它是排序题里少见的“非比较型排序”不靠两两之间比大小而是靠“分桶”和“次数”直接把数据摆到正确位置。集训安排到第十天讲它不是因为它难而是因为它是检验学生能不能跳出“比较思维”的最好试金石。这篇内容适合正在系统学排序、准备算法面试或者刷了不少排序题但总觉得“快排就是终极答案”的人阅读。我会从原理、手推案例、代码实现到负数处理这些实战坑全部拆一遍照着走一遍基本就能自己写出来了。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两条路线的取舍基数排序有两种主流路线LSDLeast Significant Digit从最低位个位开始向最高位处理。排整数时最常用实现简单代码好写适合编程教学和竞赛。MSDMost 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]第一轮按个位分桶个位 0170、90个位 2802、2个位 424个位 545、75个位 666收集后得到[170, 90, 802, 2, 24, 45, 75, 66]。注意这个序列里个位已经升序了0, 0, 2, 2, 4, 5, 5, 6。第二轮按十位分桶把上面的数组依次看170 的十位是 790 的十位是 9802 的十位是 02 的十位是 0严格说是没有十位取 024 的十位是 245 的十位是 475 的十位是 766 的十位是 6。分桶后十位 0802、2十位 224十位 445十位 666十位 7170、75十位 990收集[802, 2, 24, 45, 66, 170, 75, 90]。第三轮按百位分桶802 百位 82 百位 024 百位 045 百位 066 百位 0170 百位 175 百位 090 百位 0。分桶百位 02、24、45、66、75、90百位 1170百位 8802收集[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(vectorint arr, int exp) { int n arr.size(); vectorint output(n); vectorint 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(vectorint 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 4k 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下标直接越界。有三种常见解法偏移法找到最小值 minVal把所有数先减去 minVal转成非负数排完序再统一加回来。比如 [-5, 3, -2]minVal -5转换后为 [0, 8, 3]排序得到 [0, 3, 8]再减去 -5 得到 [-5, -2, 3]。这个方法最简单但要求数据范围不太大否则偏移量太大会浪费。正负分段法把负数取绝对值排序然后把正数部分和负数部分合并负数部分要逆序排放。补码思路对整数按二进制位处理符号位本身就参与排序不过实现起来更绕一般面试只要说得出思路就行。实战中我推荐偏移法最少改动原代码。不过要注意偏移量本身可能较大排序过程仍基于处理后的非负数整体复杂度不变。4.2 基数选择10、256 还是 2三种选择的本质是让 d 和 k 互相权衡基数桶数一轮处理的信息量轮数32位整数为例适合场景1010一位十进制数最多 10 轮教学、笔试手写、范围较小的整数256256一个字节4 轮工程实现、大数据量整数排序22一个二进制位32 轮不推荐轮数太多基数越大每轮分桶更粗轮数越少但 count 数组和内存开销越大基数太小比如 2会导致轮数爆炸。工程上取 256 是性能和使用复杂度的平衡点也便于用位运算。4.3 内存开销与大数据场景取舍当你处理千万级数据时基数排序每轮都要复制一次整个数组到 output千万整数就是几 MB 到几十 MB 的内存消耗比快排的递归栈开销要高不少。如果内存紧张基数排序的优势会被冲淡。另外对布尔类型或极窄范围的数组开 256 个桶纯属浪费直接计数排序就够了不用绕多层。这里我踩过一个坑曾经对一个 5000 万整数的数组做排序选用基数 256内存是够的但外层循环每轮都会触碰整个数组后来发现主要瓶颈反而是内存带宽。之后改成减少无谓复制比如使用两个数组交替作为输入输出而不是每轮新建一个数组才把时间压下来。4.4 常见问题速查表问题现象可能原因排查方法排序结果局部有序但整体全乱内层排序不稳定检查收集阶段是否从后往前填充count 累加位置是否准确出现负数或下标越界负数未做偏移先找最小值做偏移或单独处理负数段结果对但速度极慢基数取得太小轮数过多换用 256 或 2 的幂作为基数数组长度小但内存消耗高每轮新建 output 数组改为双数组的 in-place 交替复用空间排字符串出错字符串长度不一致短字符串补 0或者按最长长度补前导字符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 的进制数排序”之类的题目你只需要改一个参数其余逻辑纹丝不动。