计数排序（Counting Sort）实现异常：随机数组单个元素无法输出

嘿，我之前写计数排序的时候也好几次碰到过丢元素的问题，咱们一步步来排查解决，大概率是这几个常见的小错误：

1. 计数数组的长度算错了（最常见！） #

计数数组的长度需要覆盖原数组所有元素的范围，也就是 最大值 - 最小值 + 1，很多人会忘了加这个+1，导致最大的元素没有对应的计数位置，自然就丢了。

举个反例：

min_val = min(arr)
max_val = max(arr)
count = [0] * (max_val - min_val)  # 这里少了+1！

如果原数组是[3,5,7]，max-min是4，但元素范围是3、4、5、6、7，共5个值，少加1的话计数数组长度是4，7对应的索引是7-3=4，直接超出数组范围，统计不到这个元素。

正确写法：

count_size = max_val - min_val + 1
count = [0] * count_size

2. 元素到计数数组的索引偏移错了 #

当原数组元素不是从0开始时，必须用 元素值 - 最小值 来映射到计数数组的索引，如果这里算错（比如忘了减最小值，或者减错了数值），就会导致某个元素的计数被统计到错误的位置，最后输出时找不到它。

比如原数组最小值是2，元素是5，正确索引是5-2=3，如果写成5-1=4，要么超出计数数组范围，要么对应到错误的位置，计数没被正确累加。

3. 输出结果时循环边界没处理好 #

构建结果数组的时候，如果你遍历计数数组的范围是range(len(count)-1)，那最后一个索引的元素就会被漏掉。必须遍历整个计数数组的所有索引：

错误示例：

for i in range(len(count)-1):  # 少了最后一个索引
    result.extend([min_val + i] * count[i])

正确写法：

for i in range(len(count)):
    result.extend([min_val + i] * count[i])

快速排查小技巧 #

• 先看长度：打印原数组和排序后数组的长度，如果长度不一样，直接定位是统计或输出环节丢了元素；
• 打印关键值：把min_val、max_val、计数数组的长度和计数数组本身都打印出来，看看那个丢失的元素有没有被统计到；
• 单独测试丢失元素：把那个总是丢失的元素单独放进数组里跑一遍，看计数数组对应的位置有没有正确累加计数。

完整的正确示例代码 #

import random

def counting_sort(arr):
    if not arr:
        return arr
    
    min_val = min(arr)
    max_val = max(arr)
    # 正确计算计数数组长度
    count_size = max_val - min_val + 1
    count = [0] * count_size
    
    # 统计每个元素的出现次数
    for num in arr:
        index = num - min_val
        count[index] += 1
    
    # 构建排序后的数组
    sorted_arr = []
    for i in range(count_size):
        sorted_arr.extend([min_val + i] * count[i])
    
    return sorted_arr

# 测试随机数组
random_arr = [random.randint(0, 15) for _ in range(12)]
print("原数组：", random_arr)
result = counting_sort(random_arr)
print("排序后数组：", result)
print("长度校验：原数组{}个元素，排序后{}个元素".format(len(random_arr), len(result)))

你可以把自己的代码和这个示例对比，大概率能找到问题所在！

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