基数排序（Radix Sort）的详细实现与优化
字数 2300 2025-11-14 20:51:34

基数排序（Radix Sort）的详细实现与优化

基数排序是一种非比较型的整数排序算法，它通过逐位处理数字的每一位来实现排序。其核心思想是：从最低有效位（LSB）到最高有效位（MSB），依次使用稳定的排序算法（通常是计数排序）对数字进行排序。

1. 算法基本思想

想象一下排序一堆扑克牌。一种方法是先按花色（红桃、黑桃、梅花、方块）分成四堆，然后在每个花色堆里按点数排序。基数排序的思路类似，但它按数字的每一位来“分堆”。由于我们是从低位开始排序，高位数字的权重更大，所以最终高位数字的顺序会覆盖低位数字的顺序，从而达到整体有序。

2. 算法步骤详解

我们以排序数组 [170, 45, 75, 90, 2, 802, 24, 66] 为例，说明基数排序的步骤。

  • 步骤 1：找到最大值，确定最大位数
    首先，我们需要知道要排序的数字中最大的是多少，这决定了我们需要进行几轮排序。

    • 在示例数组中，最大值是 802。
    • 802 有 3 位数。因此，我们需要进行 3 轮排序，分别处理个位、十位和百位。

  • 步骤 2：从最低位（个位）开始，按当前位进行稳定排序
    这是算法的核心循环。我们使用一个稳定的排序算法（稳定是指：如果两个元素的值相同，排序后它们的相对顺序保持不变）。计数排序是常用的选择，因为它时间复杂度低且稳定。

    • 第1轮：按个位数字排序

      • 遍历数组，提取每个数字的个位数：
        [170(0), 45(5), 75(5), 90(0), 2(2), 802(2), 24(4), 66(6)]
      • 使用计数排序（或其它稳定排序）仅根据个位数字对整个数字进行排序。
      • 排序后数组为：[170, 90, 2, 802, 24, 45, 75, 66]
        • 170和90的个位都是0，它们保持了原来的相对顺序（170在90前）。
        • 2和802的个位都是2，2在原数组中就在802之前，排序后依然如此。
        • 45和75的个位都是5，也保持了相对顺序。

    • 第2轮：按十位数字排序

      • 现在对上一轮的结果 [170, 90, 2, 802, 24, 45, 75, 66] 进行处理。
      • 提取每个数字的十位数（对于不足两位的数，十位视为0）：
        [170(7), 90(9), 2(0), 802(0), 24(2), 45(4), 75(7), 66(6)]
      • 再次使用稳定的计数排序根据十位数字对整个数字进行排序。
      • 排序后数组为：[2, 802, 24, 45, 66, 170, 75, 90]
        • 注意170和75的十位都是7。在上一轮结果中，170在75之前。由于排序是稳定的，本轮排序后，170依然在75之前。

    • 第3轮：按百位数字排序

      • 对上一轮的结果 [2, 802, 24, 45, 66, 170, 75, 90] 进行处理。
      • 提取每个数字的百位数（对于不足三位的数，百位视为0）：
        [2(0), 802(8), 24(0), 45(0), 66(0), 170(1), 75(0), 90(0)]
      • 使用稳定的计数排序根据百位数字对整个数字进行排序。
      • 排序后数组为：[2, 24, 45, 66, 75, 90, 170, 802]
        • 此时数组已经完全有序。

3. 关键实现细节：使用计数排序作为子程序

基数排序的高效性依赖于子排序算法的高效和稳定。计数排序非常适合，因为它：

  • 稳定：通过从后往前遍历原数组并填充结果数组，可以保证稳定性。
  • 高效：时间复杂度为 O(n + k)，其中 k 是当前位上数字的范围（0-9，所以 k=10）。

计数排序在基数排序中的具体应用：

  1. 统计频率：创建一个大小为10（因为数字是0-9）的数组 count，统计当前位上每个数字出现的次数。
  2. 计算位置：将 count 数组进行累加，count[i] 表示当前位数字小于等于 i 的元素有多少个。这实际上确定了每个数字在输出数组中的最后位置。
  3. 从后往前排序：从原数组的末尾开始向前遍历，根据当前位数字查找 count 数组，确定该元素在输出数组中的正确位置，然后将其放入，同时将 count 中对应的值减1。这一步是保证稳定性的关键。

4. 复杂度分析

  • 时间复杂度：O(d * (n + k))

    • d 是最大数字的位数（排序的轮数）。
    • n 是数组长度。
    • k 是每一位数字的范围，对于十进制数是10。
    • 当 d 是常数且 k 是 O(n) 时，基数排序的时间复杂度可以看作是线性的 O(n)。

  • 空间复杂度：O(n + k)

    • 我们需要一个额外的输出数组（大小 O(n)）和一个计数数组（大小 O(k)）。

5. 优化与变体

  • MSD 基数排序：可以从最高有效位（MSD）开始排序。它更像是一种分治策略，先按最高位分桶，然后递归地对每个非空桶进行排序。MSD 基数排序在处理完高位后，可能不需要比较所有位，但实现更复杂，且需要处理递归。
  • 适应不同数据类型：基数排序不仅适用于整数，通过适当的键值提取方法，也可以用于排序字符串、浮点数等。
  • 基数选择：除了10进制，也可以使用2的幂次（如256进制）作为基数，这样可以通过位运算（如右移和按位与）来快速提取“位”，提高效率。

总结
基数排序是一种高效的线性时间排序算法，特别适用于排序范围很大但位数不多的整数集合。它的核心在于“按位分配，收集排序”，并通过使用稳定的计数排序作为子程序来保证正确性。理解其从低位到高位的排序过程以及计数排序如何保证稳定性，是掌握该算法的关键。

基数排序（Radix Sort）的详细实现与优化 基数排序是一种非比较型的整数排序算法，它通过逐位处理数字的每一位来实现排序。其核心思想是：从最低有效位（LSB）到最高有效位（MSB），依次使用稳定的排序算法（通常是计数排序）对数字进行排序。 1. 算法基本思想 想象一下排序一堆扑克牌。一种方法是先按花色（红桃、黑桃、梅花、方块）分成四堆，然后在每个花色堆里按点数排序。基数排序的思路类似，但它按数字的每一位来“分堆”。由于我们是从低位开始排序，高位数字的权重更大，所以最终高位数字的顺序会覆盖低位数字的顺序，从而达到整体有序。 2. 算法步骤详解 我们以排序数组 [170, 45, 75, 90, 2, 802, 24, 66] 为例，说明基数排序的步骤。 步骤 1：找到最大值，确定最大位数 首先，我们需要知道要排序的数字中最大的是多少，这决定了我们需要进行几轮排序。 在示例数组中，最大值是 802。 802 有 3 位数。因此，我们需要进行 3 轮排序，分别处理个位、十位和百位。 步骤 2：从最低位（个位）开始，按当前位进行稳定排序 这是算法的核心循环。我们使用一个 稳定 的排序算法（稳定是指：如果两个元素的值相同，排序后它们的相对顺序保持不变）。计数排序是常用的选择，因为它时间复杂度低且稳定。 第1轮：按个位数字排序 遍历数组，提取每个数字的个位数： [170(0), 45(5), 75(5), 90(0), 2(2), 802(2), 24(4), 66(6)] 使用计数排序（或其它稳定排序） 仅根据个位数字 对整个数字进行排序。 排序后数组为： [170, 90, 2, 802, 24, 45, 75, 66] 170 和 90 的个位都是0，它们保持了原来的相对顺序（170在90前）。 2 和 802 的个位都是2， 2 在原数组中就在 802 之前，排序后依然如此。 45 和 75 的个位都是5，也保持了相对顺序。 第2轮：按十位数字排序 现在对上一轮的结果 [170, 90, 2, 802, 24, 45, 75, 66] 进行处理。 提取每个数字的十位数（对于不足两位的数，十位视为0）： [170(7), 90(9), 2(0), 802(0), 24(2), 45(4), 75(7), 66(6)] 再次使用稳定的计数排序 根据十位数字 对整个数字进行排序。 排序后数组为： [2, 802, 24, 45, 66, 170, 75, 90] 注意 170 和 75 的十位都是7。在上一轮结果中， 170 在 75 之前。由于排序是稳定的，本轮排序后， 170 依然在 75 之前。 第3轮：按百位数字排序 对上一轮的结果 [2, 802, 24, 45, 66, 170, 75, 90] 进行处理。 提取每个数字的百位数（对于不足三位的数，百位视为0）： [2(0), 802(8), 24(0), 45(0), 66(0), 170(1), 75(0), 90(0)] 使用稳定的计数排序 根据百位数字 对整个数字进行排序。 排序后数组为： [2, 24, 45, 66, 75, 90, 170, 802] 此时数组已经完全有序。 3. 关键实现细节：使用计数排序作为子程序 基数排序的高效性依赖于子排序算法的高效和稳定。计数排序非常适合，因为它： 稳定 ：通过从后往前遍历原数组并填充结果数组，可以保证稳定性。 高效 ：时间复杂度为 O(n + k)，其中 k 是当前位上数字的范围（0-9，所以 k=10）。 计数排序在基数排序中的具体应用： 统计频率 ：创建一个大小为10（因为数字是0-9）的数组 count ，统计当前位上每个数字出现的次数。 计算位置 ：将 count 数组进行累加， count[i] 表示当前位数字小于等于 i 的元素有多少个。这实际上确定了每个数字在输出数组中的最后位置。 从后往前排序 ：从原数组的末尾开始向前遍历，根据当前位数字查找 count 数组，确定该元素在输出数组中的正确位置，然后将其放入，同时将 count 中对应的值减1。这一步是保证稳定性的关键。 4. 复杂度分析 时间复杂度 ：O(d * (n + k)) d 是最大数字的位数（排序的轮数）。 n 是数组长度。 k 是每一位数字的范围，对于十进制数是10。 当 d 是常数且 k 是 O(n) 时，基数排序的时间复杂度可以看作是线性的 O(n)。 空间复杂度 ：O(n + k) 我们需要一个额外的输出数组（大小 O(n)）和一个计数数组（大小 O(k)）。 5. 优化与变体 MSD 基数排序 ：可以从最高有效位（MSD）开始排序。它更像是一种分治策略，先按最高位分桶，然后递归地对每个非空桶进行排序。MSD 基数排序在处理完高位后，可能不需要比较所有位，但实现更复杂，且需要处理递归。 适应不同数据类型 ：基数排序不仅适用于整数，通过适当的键值提取方法，也可以用于排序字符串、浮点数等。 基数选择 ：除了10进制，也可以使用2的幂次（如256进制）作为基数，这样可以通过位运算（如右移和按位与）来快速提取“位”，提高效率。 总结 基数排序是一种高效的线性时间排序算法，特别适用于排序范围很大但位数不多的整数集合。它的核心在于“按位分配，收集排序”，并通过使用稳定的计数排序作为子程序来保证正确性。理解其从低位到高位的排序过程以及计数排序如何保证稳定性，是掌握该算法的关键。