企业官网建设流程全解析

1. 先把这个算法聊明白

基数排序这个算法，很多人一听名字就以为是“一堆桶，挨个扔进去再倒出来”，这个印象没错，但只说对了一半。它真正有意思的地方在于——它完全不靠比较大小来排序。你不需要知道两个数字谁大谁小，只需要看到它们的个位、十位、百位，一遍一遍按位整理，最后整体就神奇地有序了。

相比于快速排序、归并排序这类比较排序，基数排序的时间复杂度是线性的，理论上能跑出 O(n) 级别的表现。这话放在工程里很诱人，尤其是你要面对几十万、上百万条整数或者固定长度字符串的时候。我在实际项目里给订单号、时间戳、设备ID这类固定位数的数字做过排序，直接用比较排序往往要吃满 CPU，换基线排序能明显感觉到计算量被压下去，瓶颈反而变成了内存带宽。

这篇文章适合三类人：第一类是在学算法原理的新手，你可以通过基排真正理解“稳定排序”到底是什么；第二类是准备面试的开发者，除了快排、堆排、归并，基数排序是一个很有区分度的可用答案；第三类是实际工作里被大数据排序困扰的工程师，尤其是手头数据全是整数或短字符串时，这篇文章能给你一个低成本的替代方案。

整个算法的基础思路，一句话就能说清：把整数拆成一位一位的数字，从低位到高位依次排序，每排完一位，低位的顺序就被完整保留下来，等最高位排完，整个数组自然有序。

1.1 基数排序到底是什么

基数排序属于“非比较排序”家族，跟桶排序、计数排序是一伙的。它处理的对象一般是有固定“位数”概念的数据，比如十进制整数、日期字符串、固定长度的电话号码等。核心操作是：按某一位数字对所有元素做一次稳定分类，重复若干轮，直到每一位都被处理完。

关键就在这里：因为每一轮只处理一位，所以每一轮内部的排序必须是稳定的。稳定是什么概念？就是数值相同的元素，排序前后相对顺序不能变。这一点是基数排序能成立的根基，后面我专门讲。

为什么必须稳定？你用生活经验想一想：整理一沓发票，第一次按“日期个位数”排序，第二次按“日期十位数”排序，第三次按“日期百位数”排序……如果第二次排序时，把同一个月内的两张发票次序搞反了，那最后整体结果一定乱套。所以每一轮都不能破坏上一轮已经形成的次序，这就是稳定性的价值。

我不是第一次接触它时就把原理彻底想明白的。最开始我只是照抄了一个实现跑通了，面试时被追问“为什么从低位开始而不是从高位？”顿时卡壳。后来手动跟踪了几轮数据才真正理解，所以这篇里我会把为什么设计成每轮稳定排序的细节讲透，而不只是丢代码。

1.2 一个生活化的例子帮你看懂全程

有没有整理过一堆卡片？比如一个大列表，上面写满了 0 到 999 的数字，你想把卡片从小到大排整齐。一个想到的办法是给 10 个盒子，编号 0 到 9，第一遍看个位数，把卡片丢进对应盒子里，再按编号串联起来；第二遍看十位数再做一遍；第三遍看百位数再做一遍。三次之后，卡片就整齐了。

这个办法不要求你比较 158 和 162 谁大，你只需要看个位是几、十位是几、百位是几。每一次“丢盒子、串起来”的动作，都是把上一轮形成的相对顺序带进下一轮。整个过程就像在低位上先建立一种“局部次序”，然后通过稳定操作逐位放大，最终得到全局的有序序列。这就是基数排序最朴素的画面。

如果你手里是一堆单词，而不是数字，道理也一样：按最后一个字母排、按倒数第二个字母排、按倒数第三个字母排……类似地做稳定逐位整理，最后就能按字典序排好。你如果接触过字符串排序，会发现基数排序的思想在字典序问题上格外好用。

2. 基数排序的核心原理

原理部分我分两个方向讲：一个叫 LSD（Least Significant Digit，最低位优先），一个叫 MSD（Most Significant Digit，最高位优先）。实际工程里用得最多的是 LSD，我后面所有代码也会围绕 LSD 展开，但 MSD 的递归分桶思想很值得理解，面试时被问到也算一个知识增量。

2.1 LSD最低位优先：从个位开始排起

LSD 的执行逻辑非常简单，总共三步：

1. 找到数组中的最大值，算出它有几位数字，这决定要跑几轮。
2. 从最低位（个位）开始，对每一位做一次稳定的“按位归类”，通常用计数排序实现。
3. 把数组整体更新，换到下一位继续。

用一个具体例子走一遍，数组是[170, 45, 75, 90, 802, 24, 2, 66]。最大数是 802，三位数，所以需要三轮。

第一轮，按个位归类：

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

如果按个位从小到大串起来，你会得到[170, 90, 802, 2, 24, 45, 75, 66]。注意：170 和 90 的个位都是 0，因为它们在原数组中 170 出现在 90 前面，稳定排序后这个顺序不能变。

第二轮，按十位归类，上一轮的数组作为输入：

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

按十位从小到大串起来，得到[802, 2, 24, 45, 66, 170, 75, 90]。

第三轮，按百位归类：

• 百位为 0 的有 2、24、45、66、75、90
• 百位为 1 的有 170
• 百位为 8 的有 802

最终得到[2, 24, 45, 66, 75, 90, 170, 802]，完全有序。

从过程里你能看到一个关键现象：第二轮串起来后，十位为 7 的 170 排在 75 前面，这正是因为第一轮里 170 的个位 0 小于 75 的个位 5，这个低位次序被稳定保留了下来。如果某一轮把这种相对次序破坏了，后面再怎么排也补不回来。

2.2 MSD最高位优先：递归式分桶

MSD 的方向跟 LSD 正好相反，它先从最高位开始。比如一个三位数，先按百位分成三个桶：0 开头的、1 开头的、8 开头的。百位为 0 的再按十位继续分；百位为 1 的按十位继续分；百位为 8 的同理。分到最后，把所有桶按顺序合并。

听上去比 LSD 更符合人的直觉，毕竟我们平时比较数字就是从高位看起。但 MSD 在工程实现上更麻烦，因为每一层都要递归，桶数量动态增加，最坏情况内存开销会比较大。它适合的对象更多是字符串排序，因为字符串天然能按前缀分层。

LSD 我就不需要递归，只要迭代处理每一位，代码实现简单，而且每一轮都用同一套计数排序逻辑，稳定性好保证。这也是为什么实践中大家默认说“基数排序”的时候，多数指的是 LSD。

2.3 为什么稳定排序是基排的命根子

这一点我想单独拿出来说，因为它是最容易被忽略、也最容易在面试里栽跟头的点。

回忆这个思路：我们希望通过低位先建立局部次序，再靠高位排序保持下去。但“保持”不是自然发生的，是需要排序算法主动保证的。如果高位排序用的不是一个稳定算法，那么当两个元素的高位相同，它们的先后顺序可能被随意交换，最终结果就乱了。

举个例子，数组是[172, 173, 174]。第一轮按个位排，顺序是[172, 173, 174]。到第二轮按十位排，三个数的十位都是 7，稳定排序会保持[172, 173, 174]。但如果这一轮排序不稳定，完全有可能把[172, 173, 174]搅成[173, 172, 174]，第三轮按百位排时，三个数的百位又都是 1，不稳定排序依然可能打乱顺序。到最后你会得到[173, 172, 174]，数据就错了。

所以每一轮内部都必须是一个稳定的排序。基数排序里最常见的“内部零件”是计数排序，因为它不仅能保持稳定，还快。下一个小节我展开说为什么选它而不是冒泡排序、插入排序这些稳定排序。

3. 打底子：计数排序

如果没接触过计数排序，单看基数排序的代码会觉得云里雾里。计数排序专门针对取值范围有限的整数序列，比如所有元素都在 0 到 9 之间，或者 0 到 255 之间。为什么不比较也能排？因为它直接把元素值当成下标，数一遍哪个值出现了几次，然后按顺序倒出来就行。

3.1 计数排序的原理和实现

假设要对[4, 2, 2, 8, 3, 3, 1]排序，所有数在 0~9 之间。我们开一个长度为 10 的计数数组，下标就是数值本身。第一遍遍历原数组，统计频次：1 出现 1 次，2 出现 2 次，3 出现 2 次，4 出现 1 次，8 出现 1 次。第二遍，从小到大把数字按频次放回原数组，得到[1, 2, 2, 3, 3, 4, 8]。

这就是最基础的计数排序。它快，时间复杂度是 O(n + k)，其中 k 是取值范围的宽度，但它有一个“副作用”是不稳定——因为按值倒出来的时候，相同值的元素到底谁先谁后，完全取决于你怎么倒。不过我们只需要在计数数组里存“累积分段位置”，再倒序遍历原数组，就能做到稳定版本。这个稳定版是实现基数排序的关键，先记住结论。

稳定版计数排序的执行过程是这样：先统计频次，再把频次做累加，累加后的数组里存的就是“某个值最后应该落在结果数组的哪个位置”。接着从原数组的末尾往前遍历，每遇到一个元素，就放到累加位置标记的槽位里，同时把位置往前挪一格。倒序遍历这一步让后出现的元素先落位，而累加数组又保证了同样数值的元素会按原顺序落进紧挨着的位置，所以最终相对顺序就保住了。

3.2 为什么基排要选计数排序当“零件”

基数排序每一轮是在某个位上分类。十进制数字每一位的取值范围天然只有 0~9，如果你把基数改成 2 的倍数，比如按 8 位二进制一组，每一位的取值范围就是 0~255。这个范围非常固定且小。

你可以用“开 10 个桶，往桶里塞列表，然后按顺序拼接”的方式实现每一位的稳定排序。代码写起来直观，但在数据量大的时候性能很糟：每轮都要创建一堆 Python 列表对象，拼接时还要反复复制，内存碎片和开销都上来了。计数排序只需要一个固定长度的计数数组和一个输出数组，重复使用，不额外造对象，稳定性和性能都更有保障。

这也是为什么几乎所有基数排序的正经实现，内部用的都是计数排序。你可以理解为：基数排序是“外层框架”，负责控制按哪一位排；计数排序是“内层引擎”，负责真实地完成一趟稳定整理。

4. Python实现：从能跑到用好

代码部分我会分几个版本，从最容易理解的版本开始，逐步给出适合上生产环境的写法。配合前面的原理看，你会发现每一步为什么这么写是有迹可循的。

4.1 基础LSD版，先把逻辑跑通

先定义一个用于某一轮的计数排序函数，它接收数组和当前位数 exp：

def counting_sort_for_digit(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 # 统计当前位上每个数字出现的次数 for num in arr: digit = (num // 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 return output def radix_sort_lsd(arr): if not arr: return arr max_val = max(arr) exp = 1 while max_val // exp > 0: arr = counting_sort_for_digit(arr, exp) exp *= 10 return arr

这段代码里最容易写错的是倒数第二个循环的方向。为什么要从后往前遍历？因为 count 数组里存的是“该数字的最后一个元素应该落在 output 的位置”，如果从前往后遍历，前面的元素会把位置占住，后面相同数字的元素反而会落到更前面的空隙，稳定性就没了。从后往前是稳定版的标志性写法。

exp是当前位的“单位权重”，个位时 exp = 1，十位时 exp = 10，百位时 exp = 100。(num // exp) % 10取的就是对应位上的数字。这个思路可以推广到任何进制，只要把除数换成对应的基数幂即可。

4.2 用字节当基数，让32位整数只跑4趟

十进制版本直观，但一趟只处理一位十进制数字，32 位整数最多要跑 10 趟。你可以把基数从 10 换成 256，按 8 位二进制一组来排序。一个 32 位整数被拆成 4 个字节，一轮处理一个字节，最多 4 趟就能完成，速度通常会更快。

这种做法的核心是移位和掩码操作：

def counting_sort_by_byte(arr, shift): mask = 0xFF count = [0] * 256 for x in arr: count[(x >> shift) & mask] += 1 for i in range(1, 256): count[i] += count[i - 1] output = [0] * len(arr) for x in reversed(arr): byte = (x >> shift) & mask count[byte] -= 1 output[count[byte]] = x return output def radix_sort_bytes(arr): if not arr: return arr for shift in (0, 8, 16, 24): arr = counting_sort_by_byte(arr, shift) return arr

这个版本跑正整数的效果很稳定。它每一轮只需要一个长度为 256 的计数数组，空间开销比十进制版本还小。这里要注意一个坑：Python 中对负数做右移操作时是按补码形式做算术右移，负数的符号位会被扩展，导致(x >> shift) & mask出来的字节序列不符合你期望的“按大小排列”的位模式。所以这个版本如果直接用于负数列表，结果一定不对，要配合后文说的负数偏移处理。

4.3 负数与浮点数的处理方案

负数的问题本质上是：取模和位运算遇到负号后，结果不再符合我们期望的“数字位”关系。最稳妥的通用办法是给整个数组加一个偏移量，把负数全部拉成非负数，排序结束后再减回去。

具体思路是找到数组最小值，如果最小值小于 0，把每个元素都减去这个最小值。比如最小值是 -5，那所有元素减完 -5 之后都变成非负数，再跑基数排序就安全了。排完序再手动加回偏移量。这里的代价是遍历数组两遍，但换取的是对所有负数都安全的解法。

浮点数就比较麻烦了。你没法直接对小数位做% 10操作，因为浮点数不是按十进制位拆的。最常用的思路是先把浮点数转成等价的整数表示，比如乘以 1000 或 100000 再四舍五入取整，排序之后再除以同样的倍数。这在业务数据精度有限的情况下完全够用。如果你要处理的是 IEEE 754 原始浮点位模式，那属于高性能数值计算领域的玩法，这篇先不展开。

我实际工作时，多数数据是 ID 和状态码这类整数，所以偏移法最常用。它是那种“一句话能说清、五分钟改完、效果立刻可见”的解决方案。

5. 复杂度推导和基准表现

看代码之前我们先说结论：基本原则是“位数越少、取值范围越小，越适合基数排序”。为什么有这个结论，得从复杂度的推导说起。

5.1 时间复杂度的由来

每一轮计数排序遍历整个数组统计频次，再遍历计数数组做累加，还要再一次遍历数组生成输出结果。一轮的时间复杂度是 O(n + k)，其中 k 是当前排序的基数宽度，也就是计数数组的长度。

如果按十进制，k = 10；按 8 位二进制，k = 256。d 表示需要处理的位数轮数，对十进制就是最大数的十进制位数，对字节版本就是 4 或 8。总时间复杂度就是 O(d × (n + k))。

如果 n 很大，而 d 相对固定（比如排序几十万条 32 位整数，d 最多 4 轮字节排序），复杂度可以近似看成 O(n)。比较排序的 O(n log n) 在 n 大了之后增长明显更快，理论上是基排的优势所在。别急着开心，看到空间复杂度你就知道这笔账没那么容易占便宜。

5.2 空间与缓存：为什么基排常被误伤

基数排序每一轮都要一个和原数组等长的临时输出数组，再加上一个长度为 k 的计数数组。如果你做的是 in-place 版本的基数排序，依然需要一个临时缓冲区来保存每一轮的结果，因为原数组不能被部分覆盖。所以空间复杂度是 O(n + k)。

这和归并排序一样，都属于“空间换时间”的思路。实际运行中还有一个容易被忽略的短板：基数排序每一轮都在整个数组上做随机访问式的写入输出，数据量一大，缓存命中率比快速排序、归并排序差不少。尤其是 Python 这种解释型语言，如果实现不够优化，很容易出现“理论上更快，跑起来却更慢”的情况。

我自己的实际经验是：用纯 Python 写的基数排序去对比 Python 内置的sorted（底层是 C 实现的 TimSort），数据量到一百万时基排往往反而慢。这不是算法原理的问题，而是语言层实现成本的差异。纯 Python 每访问一个元素都要经过解释器，循环开销远大于 C 代码。所以想在工程里真正吃到基数排序的红利，要么用 C/Cython 写扩展，要么用 NumPy/SQL 这类偏底层的工具去处理，而不是直接在 Python 列表上裸跑。

5.3 我实测到的性能和选型判断

给个具体参考：同样是 10 万元素、范围在 0 到 1 亿的随机整数，我本地跑过三种方案：Python 内置sorted大概是 0.05 秒级别；纯 Python 基数排序按字节版大概是 0.15 到 0.3 秒级别；如果换用numpy先转成数组再用底层排序，又是另一个世界。

所以我对基数排序的建议一直是分层看：面试和算法学习里，它值得讲清楚原理、写明白代码；真实性能敏感项目里，优先考虑是否能用 NumPy 内置的np.sort、是否能把数据推到数据库或列式存储里去排。如果一定要用纯 Python 实现，最好在数据特征特别合适、数据量不是极端巨大、并且你已经确认内置排序不再够用时再上。

这不是泼凉水，而是让你手里多一把工具，但你要清楚这把工具适合在什么场合用。算法不分贵贱，关键是场景选型要用对。

6. 实战场景：哪里用得上它

理论看完了，代码也有了，我来谈几个我从真实工作里总结出的使用场景和踩坑判断。

6.1 适合基数排序的数据

第一类：大量固定位数的整数。比如订单号、流水号、用户 ID 这类本身就是数字，并且位数基本一致的字段。它们天然适合按位处理，而且位数少，跑的轮数也少。

第二类：固定长度的字符串，尤其是短字符串。比如日期字符串20240101、电话号码、身份证号这类数据，先把字符转换成对应的 ASCII 码或数字，然后按照从后往前的顺序逐位做稳定的计数排序，一样能排。这类数据看起来不像数字，但位数固定，直接套用基数排序的思路非常方便。

第三类：数量大且数值范围相对集中的整数。基数排序不关心数值是否均匀分布，只关心当前位的数字分布。这让它在某些极端不均匀数据上反而比快速排序稳定，不会出现快排那种围绕 pivot 选择而表现不稳定的情况。

我之前处理过一个多租户场景，需要按租户 ID 和订单序号组合出的复合键来排序一批流水记录。复合键本质上就是一个大整数，可以拆成两个字段分别处理。用基数排序的思路做预处理分片，比单纯用关系数据库的 ORDER BY 在内存计算里快不少。

6.2 不适合硬上的地方

数据长度差距很大的场景要小心。比如字符串长短不一，按位处理时短字符串怎么补位是个麻烦事，处理不好容易出错；数据量很小的时候，基数排序的轮数分摊到复杂度上没有优势，而且还要额外开输出数组，不如直接用插入排序或者内置排序；另外如果你不需要排序，只需要找 TopK 或者去重，做基数排序就是杀鸡用牛刀，算法选型完全不对。

再一个要留神的是：如果你的数据已经存在于数据库或者引擎里，比如 Pandas 的 DataFrame、ClickHouse、PostgreSQL，那直接用引擎内置的排序大概率更快。把数据导出到 Python 再做一轮基数排序，这属于反向优化，我在早期阶段也犯过这种错误。

7. 常见问题与排查技巧

最后把我在写基排时踩过的坑和排查经验整理成一张表，直接照着排查，能给你省不少时间。

7.1 排序结果不对，先查稳定性和位数

遇到排序结果错乱，第一反应不是去看算法逻辑，而是检查每一轮是不是稳定排序。最常见的问题是稳定版计数排序里遍历顺序写反了：从前往后遍历原数组，导致相同数字的相对位置被破坏。检查方式很简单：把计数排序单独拎出来，输入[1, 2, 2, 3]，看输出是不是[1, 2, 2, 3]，如果变成[1, 2, 3, 2]那稳定性就没了。

第二个常见问题是exp步长写得不对，导致某一位被重复处理。比如 while 循环条件写成max_val // exp > 0，但 exp 每轮乘 2 而不是乘 10，位数轮次就乱了。这里推荐在代码里临时把数组打印一下，跟踪每一轮结果，看看是不是只在正确的位数上发生变化。

7.2 负数和超长数字怎么处理

负数直接跑基数排序，得到的结果会错得非常离谱。我上面提过，最简单的方式是先整体偏移到非负数，排序完成后再偏移回去。如果数据里既有负数也有大整数，优先用字节版配合偏移，避免十进制版轮数过多。

Python 的整数是任意精度的，所以即使数字远超 32 位，代码本身并不会因为溢出崩掉，但位数会变长，跑的轮数也会变多。如果数据里混着 10 位和 20 位的数字，建议在排序前统一看一眼最大值的位数，否则你会多做几轮无意义的空转。逻辑上没错，性能上吃亏。

7.3 最常踩的几个坑

最后列一个速查表：

我自己曾经在负数排序上卡了整整一个晚上，当时数据量很大，偶尔出现局部乱序，排查了很久才发现是负数取模出来的负索引把计数数组的下标搞乱了。后来养成了一个习惯：写完基排第一件事，先用包含负数、0、重复元素、不同位数的小数据集做单元测试，跑通再放开到真实数据上。

如果说有什么心得，就是：基数排序的代码量不大，但正确性完全押在“稳定排序”和“位数正确”两个细节上，任何一个环节被忽略，排查时间都会远大于写代码时间。上手时先逼自己动手跟踪一遍数组变化，亲手写出每一轮的中间结果，比看十遍解释都管用。