AlgoNote 数组基数排序完全指南：按位分桶的线性复杂度排序算法

• 教程
• 文档
• 知识库

基数排序（Radix Sort）是 AlgoNote「算法通关手册」数组排序章节中的一种非比较排序算法，它通过"按位分配 + 按序收集"的方式，将排序时间复杂度降低到与数据范围无关的 $O(n \times k)$。本篇文章以 docs/01_array/01_12_array_radix_sort.md 为主体，结合仓库中的 Python 实现源码 与 链表变体实现，系统讲解基数排序的算法思想、执行步骤、代码实现、复杂度分析与适用场景，并串联 LeetCode 排序数组题解 与 最大间距题解 两个实战案例。读完本篇，你将掌握基数排序"最低位优先法"的完整实现细节，理解其稳定排序与线性复杂度的来源，并能在固定位数整数数据场景中正确选型。

1. 基数排序算法思想

基数排序（Radix Sort）基本思想：

按照数字的每一位进行排序，从最低位到最高位，逐位比较。

与冒泡、快速、归并等基于"比较元素大小"的排序算法不同，基数排序属于非比较排序，它与计数排序、桶排序同属线性时间排序家族（见 docs/01_array/01_02_array_sort.md 的排序算法分类）。基数排序的核心洞察是：既然一个整数可以按位拆分成多个"独立维度"，那么就可以放弃元素之间的两两比较，改为对每一位分别进行一次稳定的"分桶排序"，多轮分桶叠加后即可得到全局有序序列。

从仓库的 数组实现源码 可以直观看到，算法的全部逻辑只围绕两个操作展开：

• 按位取数字：num // (10 ** i) % 10，提取第 $i$ 位（$i=0$ 为个位）上的数字；
• 分桶收集：以该位数字为下标写入buckets[10]，再按桶序依次取出回填。

整个过程中没有任何>、<比较操作，这正是基数排序被归为"非比较排序"的代码层证据。

2. 基数排序算法步骤

基数排序算法可以采用「最低位优先法（Least Significant Digit First，LSD）」或者「最高位优先法（Most Significant Digit First，MSD）」。最常用的是「最低位优先法」。

下面我们以最低位优先法为例，讲解一下算法步骤：

1. 确定最大位数：遍历数组元素，找到数组中最大值的位数 $k$，它决定了需要进行多少轮"分桶—收集"。
2. 从最低位（个位）开始，到最高位为止，逐位对每一位进行排序：
   1. 创建 10 个桶（每个桶分别代表 $0 \sim 9$ 中的一个数字）；
   2. 按照每个元素当前位上的数字，将元素放入对应桶中；
   3. 清空原始数组，然后按照桶的顺序依次取出对应元素，重新加入到数组中。

之所以必须从最低位开始，是因为低位的排序结果会在后续高位的排序中被保留下来（前提是每轮分桶都保持稳定），最终实现"低位优先、高位定序"的完整排序效果。

2.1 完整示例演示

我们以 $[692, 924, 969, 503, 871, 704, 542, 436]$ 为例，演示基数排序的算法步骤。

第一轮：按个位（$10^0$）分桶

收集后数组变为：$[871, 692, 542, 503, 924, 704, 436, 969]$。

第二轮：按十位（$10^1$）分桶

对上一轮结果继续分桶，收集后数组变为：$[503, 704, 924, 436, 542, 969, 871, 692]$。

第三轮：按百位（$10^2$）分桶

对上一轮结果继续分桶，收集后数组变为：$[436, 503, 542, 692, 704, 871, 924, 969]$，此时数组已完全升序。

从演示可以看出：每一轮收集完成后，数组在该位及更低位的维度上就已经是有序的；三轮叠加后整体有序。这一过程的每一步都可以在仓库源码 codes/python/01_array/array_sort_radix_sort.py 的 11~18 行中找到对应实现。

3. 基数排序代码实现

3.1 数组版本：最低位优先法

仓库中 数组基数排序源码 与教程文档 01_12_array_radix_sort.md 中的代码完全一致，完整实现如下：

class Solution: def radixSort(self, nums: [int]) -> [int]: # 桶的大小为所有元素的最大位数 size = len(str(max(nums))) # 从最低位（个位）开始，逐位遍历每一位 for i in range(size): # 定义长度为 10 的桶数组 buckets，每个桶分别代表 0 ~ 9 中的 1 个数字。 buckets = [[] for _ in range(10)] # 遍历数组元素，按照每个元素当前位上的数字，将元素放入对应数字的桶中。 for num in nums: buckets[num // (10 ** i) % 10].append(num) # 清空原始数组 nums.clear() # 按照桶的顺序依次取出对应元素，重新加入到原始数组中。 for bucket in buckets: for num in bucket: nums.append(num) # 完成排序，返回结果数组 return nums def sortArray(self, nums: [int]) -> [int]: return self.radixSort(nums)

逐行拆解关键点：

• 第 3 行：size = len(str(max(nums)))通过字符串化求最大值的位数。例如max(nums) = 969时str(969)长度为 3，于是执行 3 轮分桶。这里隐含一个前提——所有元素必须为非负整数，否则str(max(nums))会因负号、小数点破坏位数的语义。
• 第 7 行：buckets = [[] for _ in range(10)]固定创建 10 个桶，对应十进制数字 $0 \sim 9$。若数据为十六进制，可扩展为 16 个桶，源码结构完全支持。
• 第 11 行：buckets[num // (10 ** i) % 10].append(num)是核心取位表达式。以num = 692, i = 1为例：692 // 10 = 69，69 % 10 = 9，即十位数字为 9。
• 第 14 行：nums.clear()清空原数组，为收集腾出位置，避免 append 时与旧元素混淆。
• 第 16~18 行：按桶下标 $0 \to 9$ 顺序取出全部元素回填，同一桶内保持原相对顺序，这是基数排序稳定性的实现来源。

3.2 可运行验证

仓库源码文件末尾附带了可直接运行的自测用例：

print(Solution().sortArray([692, 924, 969, 503, 871, 704, 542, 436]))

在仓库根目录执行即可验证：

python codes/python/01_array/array_sort_radix_sort.py

输出结果应为[436, 503, 542, 692, 704, 871, 924, 969]，与 2.1 节手推的最终结果一致。

3.3 链表变体：从数组到链表的迁移

基数排序"只关心键的位数、不依赖随机访问"的特性，使其天然适配链表结构。仓库提供了 链表基数排序实现，配套讲解见 docs/02_linked_list/02_10_linked_list_radix_sort.md。其与数组版本的核心差异在于：

• 求最大位数改为遍历链表：通过while cur:逐节点比较len(str(cur.val))得到size；
• 收集阶段重建链表：用dummy_head = ListNode(-1)哨兵节点串联各桶元素，最后head = dummy_head.next更新头指针；
• 分桶阶段同样复用buckets[cur.val // (10 ** i) % 10]取位表达式，算法内核与数组版完全一致。

这种"同一算法、两种容器"的写法，也体现了 AlgoNote 仓库"先数组、后链表"的教学组织方式。

4. 基数排序算法分析

基数排序的复杂度指标如下：

对上述指标做进一步解读：

• 时间复杂度与数据状态无关：无论数据是正序、逆序还是随机，每一轮都必须完整遍历 $n$ 个元素完成分桶与收集，共 $k$ 轮，因此最好、最坏、平均复杂度均为 $O(n \times k)$，不存在快速排序那样的退化风险。
• 空间复杂度构成：$O(n)$ 用于存放元素（分桶时元素被复制到桶中再回填），$O(k)$ 对应 10 个桶数组本身。由于 $k$ 通常很小（十进制整数位数），实际空间开销接近 $O(n)$。
• 稳定性来源：每轮分桶时元素按原数组顺序依次 append 进桶，收集时又按桶序依次取出，相等元素（指当前位数字相同）的相对次序在轮与轮之间被原样保留，因此整体稳定。

适用场景：

• 整数排序，位数不多（$k$ 较小）；
• 数据范围大但位数固定（例如 $32$ 位有符号整数范围内的大数排序）；
• 电话号码、身份证号等固定位数数据。

需要补充的局限性：经典实现只直接支持非负整数；若处理负数，需先整体偏移为非负（如统一加上最小值绝对值）或对正负部分分别排序；若处理浮点数/字符串，则需要将键映射为可逐位比较的固定长度编码，这解释了文档中"只适用于整数排序"的结论。

5. 与其他排序算法的横向对比

结合 docs/01_array/01_02_array_sort.md 的排序算法分类体系，可将基数排序放到完整谱系中定位：

其中计数排序的复杂度 $O(n + m)$ 直接受值域 $m$ 影响，当 $m$ 极大时不可用；而基数排序通过"按位拆分"把大值域问题转化为 $k$ 轮小分桶问题，这正是其在"数据范围大但位数固定"场景下优于计数排序的根本原因。

6. 实战演练：在 LeetCode 中运用基数排序

教程文档末尾给出了三道配套练习题目，仓库中均有完整题解，可用于检验对基数排序的掌握程度。

6.1 0912. 排序数组

中等难度，标签包含"数组、分治、桶排序、计数排序、基数排序、排序"。题目要求在 $1 \le nums.length \le 5 \times 10^4$、$-5 \times 10^4 \le nums[i] \le 5 \times 10^4$ 的范围内完成升序排序。由于数据允许负数，直接套用经典基数排序会遇到负数取位问题，需结合偏移处理——这也正好检验读者是否真正理解了"取位表达式"的适用前提。

6.2 0164. 最大间距

困难难度，标签包含"数组、桶排序、基数排序、排序"，是基数排序线性复杂度的典型实战案例。题解要求"在线性时间复杂度和空间复杂度的条件下"找出排序后相邻元素的最大差值，其解题思路分两步：

1. 用基数排序在 $O(n)$ 内完成数组排序（利用题目"所有元素都是非负整数、数值在 32 位有符号整数范围内"的约束，规避了负数处理问题）；
2. 线性遍历计算相邻差值并取最大值。

题解中的radixSort实现与仓库数组源码 codes/python/01_array/array_sort_radix_sort.py 逐行一致，并以max(arr[i] - arr[i - 1] for i in range(1, len(arr)))收尾，最终整体复杂度为 $O(n)$。这道题完美诠释了"数据范围大但位数固定时选基数排序"的适用场景。

6.3 0561. 数组拆分

简单难度，标签包含"贪心、数组、计数排序、排序"，可作排序算法（含计数排序）的入门巩固题。

更多排序类题目可在 docs/00_preface/00_06_categories_list.md 的"数组排序算法题目"表格中按需筛选。

7. 总结

基数排序是一种非比较排序算法，通过按位分配和收集实现排序。

• 优点：时间复杂度与数据范围无关，稳定排序，适合固定位数数据；
• 缺点：空间复杂度较高，只适用于整数排序。

一句话记忆：基数排序用"位"换"比较"——它把对 $n$ 个元素的复杂比较，转化为对 $k$ 位数字的 $k$ 轮简单分桶，从而在固定位数整数场景下获得稳定的线性时间复杂度。与计数排序相比，它不受值域上限约束；与快速排序等比较排序相比，它没有最坏退化风险，但代价是 $O(n + k)$ 的额外空间。在实际工程中，请务必确认数据满足"非负整数、位数固定且 $k$ 较小"的前提，再决定是否选用；若数据含负数或浮点数，需先做偏移或编码转换，这正是 最大间距题解 特意强调"所有元素都是非负整数"的原因。掌握这一选型判断，你就能像仓库中 数组实现 与 链表实现 展示的那样，让同一套分桶思想在不同数据结构上自由迁移。

• 教程
• 文档
• 知识库