基数排序（Radix Sort）的进阶应用：对包含负数的整数数组进行排序
字数 2135 2025-12-06 05:05:06

基数排序（Radix Sort）的进阶应用：对包含负数的整数数组进行排序

题目描述
标准的基数排序（Radix Sort）通常用于对非负整数数组进行排序，其核心思想是从最低位到最高位（LSD，最低有效位优先）或从最高位到最低位（MSD，最高有效位优先）逐位进行稳定的计数排序。
本题要求扩展基数排序，使其能够正确处理包含负数的整数数组。例如，输入数组为 [170, -45, 75, -90, 802, 24, 2, 66]，排序后应得到 [-90, -45, 2, 24, 66, 75, 170, 802]。

解题过程循序渐进讲解

步骤1：回顾标准基数排序（非负数版本）

  1. 基数排序假设每个整数由若干“位”组成（可以是十进制位，也可以是二进制位或其他进制）。
  2. 常用LSD（Least Significant Digit）方式：从最低位开始，对每一位进行一次稳定的排序（通常用计数排序作为子程序）。
  3. 例如对非负数组 [170, 45, 75, 90, 802, 24, 2, 66] 排序：
    • 先按个位排序（0、5、5、0、2、4、2、6）→ [170, 90, 802, 2, 24, 45, 75, 66]
    • 再按十位排序（忽略个位）→ [802, 2, 24, 45, 66, 170, 75, 90]
    • 最后按百位排序 → [2, 24, 45, 66, 75, 90, 170, 802]

步骤2：问题分析——负数带来的挑战

  1. 整数在计算机中以补码表示，最高位是符号位（1表示负数，0表示非负数）。
  2. 如果直接按位排序（尤其是二进制位），负数的高位是1，会排在正数（高位为0）后面，导致错误顺序。
  3. 例如用LSD按二进制位排序，负数会排在正数之后，而不是按实际数值大小排序。
  4. 我们需要将负数转换为可比较的无符号形式，或者分别处理负数和非负数。

步骤3：解决方案1——偏移量法（最常用）

  1. 思路：将所有数加上一个偏移量（offset），使最小负数变为非负数，排序后再减去偏移量。
  2. 具体步骤：
    a. 遍历数组，找到最小值 minVal（可能是负数）。
    b. 设偏移量 offset = -minVal，使 minVal + offset = 0。
    c. 将所有元素加上 offset，得到非负数组。
    d. 对这个非负数组执行标准基数排序。
    e. 排序后，将所有元素减去 offset，恢复原值。
  3. 示例：数组 [170, -45, 75, -90, 802, 24, 2, 66]
    • minVal = -90，offset = 90
    • 加偏移后：[260, 45, 165, 0, 892, 114, 92, 156]
    • 排序后：[0, 45, 92, 114, 156, 165, 260, 892]
    • 减偏移后：[-90, -45, 2, 24, 66, 75, 170, 802] ✅

步骤4：解决方案2——分离处理法

  1. 思路：将数组分为负数和非负数两部分，分别排序后合并。
  2. 具体步骤：
    a. 分离负数和非负数。
    b. 对负数部分取绝对值，然后进行标准基数排序，得到绝对值从小到大的序列。
    c. 由于负数绝对值越大实际值越小（如-90 < -45），所以对排序后的负数部分反转顺序，再恢复负号。
    d. 对非负数部分直接进行标准基数排序。
    e. 合并两部分（负数在前，非负数在后）。
  3. 示例：同上数组
    • 负数：[-45, -90] → 绝对值 [45, 90] → 排序后 [45, 90] → 反转 [90, 45] → 恢复负号 [-90, -45]
    • 非负数：[170, 75, 802, 24, 2, 66] → 排序后 [2, 24, 66, 75, 170, 802]
    • 合并：[-90, -45, 2, 24, 66, 75, 170, 802] ✅

步骤5：实现细节（以偏移量法为例，LSD基数排序，十进制位）

  1. 计数排序子函数（针对某一位）：
    • 输入：数组 arr，当前位 exp（1, 10, 100, ...）
    • 统计每个数字（0-9）的出现次数。
    • 计算前缀和，得到每个数字的结束位置。
    • 从后向前遍历原数组，放入输出数组的对应位置（保证稳定性）。
  2. 主函数：
    • 找最小值，加偏移量。
    • 找最大值，确定最大位数。
    • 对每一位调用计数排序。
    • 减偏移量，恢复原值。

步骤6：复杂度分析

  1. 时间复杂度：O(d * (n + k))，其中 n 是元素个数，d 是最大位数，k 是进制数（十进制则 k=10）。
  2. 空间复杂度：O(n + k)（计数排序需要输出数组和计数数组）。
  3. 扩展负数处理不改变渐近复杂度，仅增加 O(n) 的偏移量操作。

步骤7：边界情况与注意事项

  1. 全部是负数或全部是非负数时，算法仍正确。
  2. 偏移量可能导致整数溢出（如果最小值是 Integer.MIN_VALUE，加偏移会溢出）。解决方案：
    • 使用更大类型（如 long）存储偏移后的值。
    • 或采用分离处理法避免溢出。
  3. 如果数值范围极大但元素很少，基数排序可能不如比较排序高效，需根据数据特征选择算法。
基数排序（Radix Sort）的进阶应用：对包含负数的整数数组进行排序 题目描述 标准的基数排序（Radix Sort）通常用于对 非负整数 数组进行排序，其核心思想是从最低位到最高位（LSD，最低有效位优先）或从最高位到最低位（MSD，最高有效位优先）逐位进行稳定的计数排序。 本题要求 扩展基数排序，使其能够正确处理包含负数的整数数组 。例如，输入数组为 [170, -45, 75, -90, 802, 24, 2, 66] ，排序后应得到 [-90, -45, 2, 24, 66, 75, 170, 802] 。 解题过程循序渐进讲解 步骤1：回顾标准基数排序（非负数版本） 基数排序假设每个整数由若干“位”组成（可以是十进制位，也可以是二进制位或其他进制）。 常用LSD（Least Significant Digit）方式：从最低位开始，对每一位进行一次稳定的排序（通常用计数排序作为子程序）。 例如对非负数组 [170, 45, 75, 90, 802, 24, 2, 66] 排序： 先按个位排序（0、5、5、0、2、4、2、6）→ [170, 90, 802, 2, 24, 45, 75, 66] 再按十位排序（忽略个位）→ [802, 2, 24, 45, 66, 170, 75, 90] 最后按百位排序 → [2, 24, 45, 66, 75, 90, 170, 802] 步骤2：问题分析——负数带来的挑战 整数在计算机中以补码表示，最高位是符号位（1表示负数，0表示非负数）。 如果直接按位排序（尤其是二进制位），负数的高位是1，会排在正数（高位为0）后面，导致错误顺序。 例如用LSD按二进制位排序，负数会排在正数之后，而不是按实际数值大小排序。 我们需要 将负数转换为可比较的无符号形式 ，或者 分别处理负数和非负数 。 步骤3：解决方案1——偏移量法（最常用） 思路：将所有数加上一个偏移量（offset），使最小负数变为非负数，排序后再减去偏移量。 具体步骤： a. 遍历数组，找到最小值 minVal （可能是负数）。 b. 设偏移量 offset = -minVal ，使 minVal + offset = 0 。 c. 将所有元素加上 offset ，得到非负数组。 d. 对这个非负数组执行标准基数排序。 e. 排序后，将所有元素减去 offset ，恢复原值。 示例：数组 [170, -45, 75, -90, 802, 24, 2, 66] minVal = -90 ， offset = 90 加偏移后： [260, 45, 165, 0, 892, 114, 92, 156] 排序后： [0, 45, 92, 114, 156, 165, 260, 892] 减偏移后： [-90, -45, 2, 24, 66, 75, 170, 802] ✅ 步骤4：解决方案2——分离处理法 思路：将数组分为负数和非负数两部分，分别排序后合并。 具体步骤： a. 分离负数和非负数。 b. 对负数部分 取绝对值 ，然后进行标准基数排序，得到 绝对值从小到大 的序列。 c. 由于负数绝对值越大实际值越小（如-90 < -45），所以对排序后的负数部分 反转顺序 ，再恢复负号。 d. 对非负数部分直接进行标准基数排序。 e. 合并两部分（负数在前，非负数在后）。 示例：同上数组 负数： [-45, -90] → 绝对值 [45, 90] → 排序后 [45, 90] → 反转 [90, 45] → 恢复负号 [-90, -45] 非负数： [170, 75, 802, 24, 2, 66] → 排序后 [2, 24, 66, 75, 170, 802] 合并： [-90, -45, 2, 24, 66, 75, 170, 802] ✅ 步骤5：实现细节（以偏移量法为例，LSD基数排序，十进制位） 计数排序子函数（针对某一位）： 输入：数组 arr ，当前位 exp （1, 10, 100, ...） 统计每个数字（0-9）的出现次数。 计算前缀和，得到每个数字的结束位置。 从后向前遍历原数组，放入输出数组的对应位置（保证稳定性）。 主函数： 找最小值，加偏移量。 找最大值，确定最大位数。 对每一位调用计数排序。 减偏移量，恢复原值。 步骤6：复杂度分析 时间复杂度：O(d * (n + k))，其中 n 是元素个数，d 是最大位数，k 是进制数（十进制则 k=10）。 空间复杂度：O(n + k)（计数排序需要输出数组和计数数组）。 扩展负数处理不改变渐近复杂度，仅增加 O(n) 的偏移量操作。 步骤7：边界情况与注意事项 全部是负数或全部是非负数时，算法仍正确。 偏移量可能导致整数溢出（如果最小值是 Integer.MIN_VALUE ，加偏移会溢出）。解决方案： 使用更大类型（如 long ）存储偏移后的值。 或采用分离处理法避免溢出。 如果数值范围极大但元素很少，基数排序可能不如比较排序高效，需根据数据特征选择算法。