基数排序（Radix Sort）的LSD与MSD实现对比 基数排序是一种非比较型的整数排序算法，其核心思想是将待排序的元素按照其键值的每一位（或每几位）的数字来分配和收集，从最低有效位（LSD）或最高有效位（MSD）开始，逐次对每一位进行排序，最终得到一个有序序列。LSD和MSD是基数排序的两种主要实现方式，它们在处理流程、性能特性和适用场景上有着显著区别。 一、 算法基础与核心思想 在深入对比之前，我们首先要理解基数排序赖以工作的两个基石： 稳定性（Stability） ：这是基数排序算法的生命线。它要求排序算法在对待排序键值相同的元素时，能够保持它们在输入序列中的相对顺序。例如，如果输入是 [ (1, 'a'), (2, 'b'), (1, 'c') ] ，按第一个数字键排序后，结果必须是 [ (1, 'a'), (1, 'c'), (2, 'b') ] ， (1, 'a') 仍然在 (1, 'c') 之前。只有保证了稳定性，当我们对高位进行排序时，低位已经排好的顺序才不会被打乱。 位（Digit）的概念 ：基数排序不直接比较整个数字的大小，而是将数字“拆解”成一个个独立的位。这个“位”可以是我们熟悉的十进制位，也可以是二进制位、字节，甚至是用于字符串的字符。排序的“轮数”取决于最大键值的位数。 二、 LSD（最低位优先）基数排序 LSD方式从键值的最右边（最低位）开始，逐步向最高位进行排序。 详细步骤（以十进制数字排序为例） 假设待排序数组为： [170, 45, 75, 90, 2, 24, 802, 66] 步骤1：找到最大值，确定最大位数 最大值为802，有3位。所以我们需要进行3轮排序（个位、十位、百位）。 步骤2：第一轮排序（按个位数） 分配（Distribution） ：创建10个桶（对应数字0-9）。遍历数组，根据每个元素的个位数，将其放入对应的桶中。 桶0: 90 桶2: 2, 802 桶4: 24 桶5: 45, 75 桶6: 66 桶7: 170 收集（Collection） ：按桶号0到9的顺序，依次将桶中的元素取出，放回原数组。 新数组: [90, 2, 802, 24, 45, 75, 66, 170] 注意 ：此时数组看起来更乱了，但个位数相同的数（如45和75）保持了原有的相对顺序（45在75之前）。 步骤3：第二轮排序（按十位数） 分配 ：对上一轮得到的新数组，根据十位数放入桶中。（对于没有十位的数，如2，其十位数视为0）。 桶0: 2, 802 桶2: 24 桶4: 45 桶6: 66 桶7: 75, 170（注意170的十位是7） 桶9: 90 收集 ：按桶号顺序收集。 新数组: [2, 802, 24, 45, 66, 75, 170, 90] 步骤4：第三轮排序（按百位数） 分配 ：根据百位数放入桶中。（没有百位的数，百位数视为0）。 桶0: 2, 24, 45, 66, 75, 90 桶1: 170 桶8: 802 收集 ：按桶号顺序收集。 最终有序数组: [2, 24, 45, 66, 75, 90, 170, 802] LSD的特点 过程 ：必须从最低位到最高位，一轮一轮进行，不能省略任何一轮。 结果 ：每一轮排序后，数组在“当前已处理过的所有位”上是有序的。 实现 ：通常使用计数排序（Counting Sort）作为子程序来高效地完成每一轮的分配和收集，时间复杂度为 O(n)。 要求 ： 必须使用稳定的排序算法作为子程序 。 三、 MSD（最高位优先）基数排序 MSD方式从键值的最左边（最高位）开始排序，然后递归地对每个“桶”内的数据进行下一位的排序。 详细步骤（同样以 [170, 45, 75, 90, 2, 24, 802, 66] 为例） 步骤1：第一轮排序（按百位数） 分配 ：创建10个桶，根据百位数分配。 桶0: 45, 75, 90, 2, 24, 66（所有百位为0或没有百位的数） 桶1: 170 桶8: 802 此时不立即进行全局收集 。我们进入下一步：递归排序。 步骤2：递归排序各个桶 对于桶1（170）和桶8（802） ：每个桶里只有一个元素，自然有序，无需再排。直接收集。 对于桶0（[ 45, 75, 90, 2, 24, 66]） ：这是一个新的待排序序列。我们递归地对这个序列进行 下一轮（十位数） 的MSD排序。 子排序-分配（按十位） : 子桶0: 2 子桶2: 24 子桶4: 45 子桶6: 66 子桶7: 75 子桶9: 90 子排序-递归 ：对每个十位桶，如果桶内元素多于1个且还有下一位（个位），则继续递归。本例中，所有十位桶都只有一个元素，所以递归终止。 子排序-收集 ：收集桶0的子桶，得到有序序列 [2, 24, 45, 66, 75, 90] 。 步骤3：全局收集 将递归排序后的所有桶按顺序连接起来： 桶0的结果 + 桶1 + 桶8 最终结果： [2, 24, 45, 66, 75, 90, 170, 802] MSD的特点 过程 ：采用分治策略，递归进行。高位优先级最高。 性能 ： 不需要处理所有的位 。一旦某个桶在高层级已经区分开，就不再需要处理其低位。这在数据分布不均匀时（例如很多数字高位相同）可能带来优势。但在最坏情况下（所有键值位数相同），性能与LSD相同。 实现 ：实现比LSD稍复杂，需要管理递归调用。同样需要稳定的分配过程。 空间 ：递归调用需要额外的栈空间。 四、 LSD与MSD的对比总结 | 特性 | LSD基数排序 | MSD基数排序 | | :--- | :--- | :--- | | 排序方向 | 从最低有效位到最高有效位 | 从最高有效位到最低有效位 | | 算法范式 | 迭代（Iterative） | 递归（Recursive），分治 | | 过程特点 | 必须完成所有位的排序 | 可能提前终止（如果某桶已区分开） | | 性能 | 稳定，时间复杂度严格为 O(d * n) ，其中d为最大位数 | 性能与数据分布有关，最好情况优于LSD，最坏情况相同 | | 实现难度 | 相对简单，易于理解 | 稍复杂，需要处理递归 | | 空间开销 | 主要来自计数排序的辅助数组，通常为O(n + k)，k为基数（如10） | 除了辅助数组，还有递归调用的栈空间开销 | | 适用场景 | 更通用，尤其适合位数固定的整数类型（如32位整数） | 适合字符串字典序排序、位数可能不同的情况（如单词排序） | 五、 关键要点与常见误区 稳定性是核心 ：无论LSD还是MSD，用于每一位排序的子程序（通常是计数排序） 必须是稳定的 ，否则整个算法会失败。 LSD的直观性 ：LSD之所以能从低位开始排最终得到整体有序，完全依赖于稳定性。每一轮排序都是在为更高位的排序“打基础”，而不会破坏之前建立的低位顺序。 MSD与快速排序的类比 ：MSD很像快速排序，都是基于最高位（主元）进行划分。区别在于，MSD的划分是基于固定范围的“位”，而快排的划分是基于比较选出的主元。 并非所有类型都适用 ：基数排序主要适用于整数、字符串等可以分解为有限“位”的数据类型。对于浮点数或复杂对象，直接应用较为困难。 通过以上循序渐进的讲解，你可以清晰地看到LSD和MSD基数排序虽然共享同一核心思想，但在实现路径和性能特性上走上了不同的道路。理解它们的差异有助于你在实际场景中做出最合适的选择。