基数排序如何处理负数？

Question

基数排序如何处理负数？一个常见的技术问题是：标准的基数排序基于每位数字进行桶分配，通常仅适用于非负整数。当输入数据包含负数时，直接按位排序会导致顺序错误，因为负数的补码表示和符号位会影响排序结果。如何在保持线性时间复杂度的同时正确处理负数？常见解决方案包括将所有数整体偏移使数值非负、分离正负数分别排序后合并，或扩展桶空间以支持符号位处理。这些方法各有性能与实现复杂度权衡，是实际应用中需重点考虑的问题。

Answer 1

基数排序如何处理负数？深入解析与多维度解决方案

1. 基数排序基础回顾

基数排序（Radix Sort）是一种非比较型整数排序算法，其核心思想是按位（从低位到高位或反之）将整数分配到“桶”中，再依次回收，最终实现有序排列。它的时间复杂度为 O(d × n)，其中 d 是数字的位数，n 是元素个数，在整数范围固定时可视为线性时间。

标准实现通常基于十进制或二进制位操作，适用于非负整数。然而，当输入包含负数时，直接应用会导致逻辑错误，因为：

• 负数在计算机中以补码形式存储，符号位参与排序会打乱自然顺序。
• 例如：-1 的补码在32位系统中为全1，若按位排序会被误认为是极大正数。

2. 负数带来的挑战分析

数值	二进制表示（8位示例）	问题表现
-3	11111101	高位为1，被误判为“大数”
-1	11111111	比所有正数都“大”
0	00000000	正常
2	00000010	正常
5	00000101	正常

如上表所示，若直接对补码进行基数排序，负数会因最高位为1而被排在正数之后，导致顺序完全颠倒。

3. 解决方案一：整体偏移法（Offset Method）

该方法通过将所有数值统一加上一个偏移量，使其变为非负数，排序后再减去偏移量还原。

def radix_sort_with_offset(arr):
    if not arr:
        return arr
    min_val = min(arr)
    offset = -min_val  # 使最小值变为0
    shifted = [x + offset for x in arr]
    sorted_shifted = radix_sort_non_negative(shifted)
    return [x - offset for x in sorted_shifted]

优点：实现简单，复用原有非负基数排序逻辑；缺点：需额外遍历求最小值，且可能溢出（尤其使用大整数时）。

4. 解决方案二：正负分离法（Separate and Merge）

将数组分为负数和非负数两部分，分别排序后合并。负数部分需逆序输出以保证升序。

1. 遍历原数组，分离负数与非负数。
2. 对负数取绝对值后排序，再逆序得到降序负数序列。
3. 对非负数正常排序。
4. 合并：先放排序后的负数（逆序），再放非负数。

示例代码片段：

negatives = sorted([abs(x) for x in arr if x < 0], reverse=True)
positives = radix_sort_non_negative([x for x in arr if x >= 0])
result = [-x for x in negatives] + positives

5. 解决方案三：扩展桶空间法（Sign-aware Radix）

在二进制基数排序中，将符号位作为最高有效位（MSB）单独处理。修改桶分配策略，使符号位决定前后半区。

graph TD A[开始] --> B{读取符号位} B -- 符号位为1(负数) --> C[放入前128个桶] B -- 符号位为0(正数) --> D[放入后128个桶] C --> E[对负数部分按补码剩余位排序] D --> F[对正数部分正常排序] E --> G[合并结果] F --> G G --> H[输出有序序列]

此方法可在一次完整基数排序中完成，无需额外预处理，但需调整桶索引映射逻辑。

6. 性能对比与适用场景分析

方法	时间复杂度	空间复杂度	实现难度	适用场景
整体偏移	O(d×n)	O(n)	低	数据范围小、无溢出风险
正负分离	O(d×n)	O(n)	中	负数比例高，需稳定排序
扩展桶空间	O(d×n)	O(n)	高	高性能要求、底层优化场景

三种方法均保持线性时间复杂度，但在实际工程中需根据数据分布、内存限制和性能需求权衡选择。