如何修改仅支持正整数的counting sort以适配负整数排序？

没问题！计数排序处理负数的核心就是把负数映射到非负的索引空间——毕竟计数数组的下标没法是负数对吧？我给你拆解几个关键修改步骤，再结合代码示例帮你理解：

核心思路：偏移量映射 #

计数排序的本质是用数组下标对应待排序的数值，所以只要把所有负数通过一个固定的偏移量“平移”到非负区间，就能复用原来的正整数排序逻辑，最后再把结果平移回去就行。

具体修改步骤 #

• 第一步：找到数组的最小值和最大值
  原来处理正整数时可能只需要最大值，但现在必须同时找到min_val和max_val——最小值用来计算偏移量，最大值用来确定计数数组的覆盖范围。
  比如待排序数组是[-5, 2, -3, 0]，min_val=-5，max_val=2。

• 第二步：计算偏移量和计数数组长度
  偏移量取-min_val（也就是把最小的负数刚好映射到索引0），上面的例子里偏移量就是5。
  计数数组的长度需要覆盖从min_val到max_val的所有整数，所以长度是max_val - min_val + 1，例子里就是2 - (-5) +1=8，对应索引0到7，分别映射原数-5到2。

• 第三步：修改统计和重构逻辑
  统计每个数的出现次数时，把原数加上偏移量得到对应的计数数组索引；重构排序结果时，把计数数组的索引减去偏移量还原成原数。

代码示例（Python） #

下面是修改后的完整计数排序实现，支持正负整数混合的情况：

def counting_sort_with_negatives(arr):
    if not arr:
        return arr
    
    # 获取数组的最小和最大值
    min_val = min(arr)
    max_val = max(arr)
    
    # 计算偏移量和计数数组的长度
    offset = -min_val
    count_length = max_val - min_val + 1
    count = [0] * count_length
    
    # 统计每个数值的出现次数（映射到非负索引）
    for num in arr:
        count[num + offset] += 1
    
    # 重构排序后的数组（还原原数值）
    sorted_arr = []
    for i in range(count_length):
        original_num = i - offset
        sorted_arr.extend([original_num] * count[i])
    
    return sorted_arr

测试验证 #

比如测试数组[-5, 2, -3, 0, -5, 2]，运行后会返回[-5, -5, -3, 0, 2, 2]，完全符合预期。如果数组全是负数（比如[-3, -1, -2]），也能正确排序成[-3, -2, -1]。

内容的提问来源于stack exchange，提问作者muumbaji