基数排序的进阶应用：对包含负数的整数数组进行排序 题目描述 给定一个整数数组，其中可能包含正数、负数和零，要求使用基数排序算法对数组进行升序排序。基数排序通常用于非负整数，现在需要扩展其能力，使其能够正确处理包含负数的整数数组。 解题过程 1. 理解基数排序的核心原理 基数排序是一种非比较型排序算法，通过逐位处理数字的每一位（从最低位到最高位）进行排序。对于非负整数，通常使用最低位优先（LSD）的方式，通过桶排序（或计数排序）稳定地排序每一位。 2. 分析负数对排序的挑战 负数的二进制表示（如补码）与正数不同，直接按位排序会导致错误（例如负数会排在正数之后，但数值可能更小）。 需要将负数映射到可排序的范围，或调整排序逻辑以兼容负数。 3. 解决方案：分离正负数并分别处理 步骤1：分离正负数组 遍历原数组，将负数（包括零）和非负数分成两个数组： non_negatives ：包含所有非负数（≥0）。 negatives ：包含所有负数（ <0）。 步骤2：处理负数数组 对负数数组 negatives 中的每个数取绝对值（例如 -5 变为 5 ），然后使用标准基数排序对绝对值排序。 排序后，由于负数的大小关系与绝对值相反（例如 -3 比 -5 大），需将排序后的负数数组反转，再恢复符号（例如排序后的绝对值数组 [3,5] 反转并加负号得到 [-5,-3] ）。 步骤3：处理非负数数组 直接对 non_negatives 使用标准基数排序（按位桶排序）。 步骤4：合并结果 最终顺序为：处理后的负数数组（已升序） + 处理后的非负数数组（已升序）。 4. 关键细节：基数排序的位处理 基数排序需要确定最大数字的位数（用于控制排序轮次）。 对于负数取绝对值后的数组，需以绝对值中的最大值为准计算位数。 每一轮排序时，使用10个桶（0-9）按当前位数字分配元素，保持稳定性。 5. 示例演示 假设数组为 [3, -2, 1, -5, 0] ： 分离： non_negatives = [3, 1, 0] ， negatives = [-2, -5] 。 处理负数：取绝对值得 [2, 5] → 基数排序后为 [2, 5] → 反转并恢复符号得 [-5, -2] 。 处理非负数：基数排序 [0, 1, 3] 。 合并： [-5, -2, 0, 1, 3] 。 6. 时间复杂度与空间复杂度 时间复杂度：O(d·(n + k))，其中 d 为最大位数， k 为基数（10）， n 为元素个数。 空间复杂度：O(n + k)（用于桶的额外空间）。 通过这种分离和映射策略，基数排序可高效处理包含负数的整数数组，同时保持稳定性和线性时间复杂度。