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

题目描述
给定一个包含正数、负数和零的整数数组，要求使用基数排序（Radix Sort）对数组进行升序排序。例如，输入数组为 [170, -45, 75, -90, 2, -802, 24]，排序后应得到 [-802, -90, -45, 2, 24, 75, 170]。

解题过程

步骤1：理解基数排序的局限性
基数排序通常用于非负整数排序，其核心思想是按数位（个位、十位、百位等）进行稳定排序（如计数排序）。但负数存在时，直接按位排序会导致错误结果，因为负数的最高位（符号位）在二进制补码表示中与其他位含义不同。

步骤2：处理负数的关键思路

1. 分离正数和负数：将数组分为负数和非负数（包括零）两部分。
2. 分别处理负数：
   • 对负数部分取绝对值，然后使用基数排序按位排序。
   • 由于负数绝对值越大，实际值越小（如 -90 比 -45 小），排序后的负数部分需要反转顺序。
3. 合并结果：将反转后的负数部分与非负数部分拼接。

步骤3：具体实现步骤

1. 分离正负数：

   • 遍历数组，将负数存入列表 negative，非负数存入列表 non_negative。
   • 示例：

     输入: [170, -45, 75, -90, 2, -802, 24]  
     negative: [-45, -90, -802]  
     non_negative: [170, 75, 2, 24]  
     

2. 对负数部分排序：

   • 将 negative 中每个数取绝对值：[45, 90, 802]。
   • 使用基数排序对该列表排序（按个位、十位、百位等）：
     • 个位排序：[90, 802, 45] → 按十位：[802, 45, 90] → 按百位：[45, 90, 802]。
   • 将排序后的绝对值列表反转（因为负数需要按绝对值降序）：[802, 90, 45]。
   • 恢复负号：[-802, -90, -45]。

3. 对非负数部分排序：

   • 直接使用基数排序对 non_negative 排序，得到 [2, 24, 75, 170]。

4. 合并结果：

   • 将负数部分 [-802, -90, -45] 与非负数部分 [2, 24, 75, 170] 拼接，得到最终结果。

步骤4：基数排序的位处理优化

• 对于负数绝对值排序，需统一数位长度（如补零到最大数字的位数），避免比较时出错。
• 实际代码中可通过计算最大绝对值确定需要处理的位数。

步骤5：复杂度分析

• 时间复杂度：O(d * (n + k))，其中 d 为最大位数，k 为基数（通常取10），n 为数组长度。
• 空间复杂度：O(n + k)，用于计数排序的临时数组和桶。

总结
通过分离正负数、分别处理并合并，基数排序可高效支持包含负数的整数排序，且保持稳定性与线性时间复杂度。