计数排序

计数排序：像整理积木一样快

计数排序是什么？用来干什么？

你玩过整理积木吗？如果积木只有几种颜色，你会把相同颜色的扔进一个篮子里，最后按颜色顺序倒出来——这样不用比较大小就能排好。计数排序用的就是这种思路：它不比较数字大小，而是直接统计每个数字出现了几次，然后按数字从小到大的顺序“倒出来”。它非常适合数字范围不大、并且都是整数的场景，比如：

全班同学的语文考试成绩（0～100分）
一个班里所有人的年龄（比如 6～12岁）
粉丝投票的序号（1～1000号）
商品尺码（S、M、L 用数字1、2、3表示）

计数排序快得像变魔术，但要小心：如果数字范围太大（比如从1到10亿），它会吃掉太多内存，就不灵了。

核心思想：不比较，直接“数数”

平时我们用的冒泡排序、选择排序，每次都要拿两个数比大小。计数排序呢？它先准备一排“盒子”，每个盒子对应一个数字。然后挨个看数组里的数，遇到哪个数，就往对应的盒子里扔一颗豆子。最后，按盒子顺序数一数每个盒子有几颗豆子，再把这些豆子代表的数字依次写出来。

生活例子：班里选班长，有5个候选人，编号1～5。老师让同学们投票，投票箱里有一堆纸条。老师不拆开纸条一个一个比较谁多谁少，而是先准备好5个桶，每个桶贴上候选人的编号。然后老师拿出一张纸条，看一眼是几号，就扔进几号桶。全部投完后，老师按桶的顺序，从1号桶开始倒出所有纸条，再倒2号桶……最后就得到了按候选人编号排好序的投票结果。

图解过程：从数字到排序

比如我们要排序的数组是：[4, 2, 2, 5, 3, 3, 1]

第1步：找范围
找出最小值是 1，最大值是 5。我们需要一个能装下 1 到 5 一共 5 个数字的“统计表”。可以想象成5个小格子，编号从 1 到 5。

第2步：统计每个数字出现的次数
遍历数组中的每个数：

遇到 4 → 4号格子加1
遇到 2 → 2号格子加1
遇到 2 → 2号格子再加1 → 现在2号格子有2颗豆子
遇到 5 → 5号格子加1
遇到 3 → 3号格子加1
遇到 3 → 3号格子再加1 → 3号格子有2颗豆子
遇到 1 → 1号格子加1

最终每个格子里的豆子数（出现次数）是：

数字	1	2	3	4	5
次数	1	2	2	1	1

第3步：按顺序输出
从最小的数字1开始：1号格子有1个，输出 1
接着2号格子有2个，输出 2, 2
3号格子有2个，输出 3, 3
4号格子有1个，输出 4
5号格子有1个，输出 5

最终得到有序数组：[1, 2, 2, 3, 3, 4, 5] ✅

Python代码实现（带详细中文注释）

下面是一个完整的计数排序函数，用到了“偏移量”技巧，可以处理最小值不是0的情况（比如年龄从6岁开始）。

def counting_sort(arr):
    # 如果数组为空，直接返回
    if not arr:
        return arr
    
    # 1. 找出最大值和最小值，确定数字范围
    min_val = min(arr)              # 最小值
    max_val = max(arr)              # 最大值
    range_of_values = max_val - min_val + 1   # 一共需要几个“盒子”
    
    # 2. 创建“统计表”（计数数组），初始全部为0
    count = [0] * range_of_values   # 统计表，下标对应数字
    
    # 3. 统计每个数字出现的次数
    for num in arr:
        # 把数字映射到统计表的下标：数 - 最小值
        index = num - min_val       # 比如数字6，最小值4，那么下标就是2
        count[index] += 1           # 对应格子加1
    
    # 4. 根据统计结果，按顺序输出到新列表
    sorted_arr = []                 # 存放排序后的结果
    for i in range(range_of_values):
        # i + min_val 就是当前盒子对应的实际数字
        # 比如i=2，最小值=4，那么实际数字 = 2+4 = 6
        sorted_arr.extend([i + min_val] * count[i])  # 重复这个数字 count[i] 次
    
    return sorted_arr

# 测试一下
test_list = [4, 2, 2, 5, 3, 3, 1]
print("排序前:", test_list)
print("排序后:", counting_sort(test_list))

运行结果：

排序前: [4, 2, 2, 5, 3, 3, 1]
排序后: [1, 2, 2, 3, 3, 4, 5]

新手容易犯的错误

忘记考虑最小值不是0
如果数组最小值是6，最大值是10，你直接建一个 count = [0] * (max_val+1) 就会浪费前面6个格子。更糟的是，数字6会存到 count[6]，而数组只到 max_val，可能会越界。正确做法：总是用 max_val - min_val + 1 作为统计表大小，并用 num - min_val 作为下标。
统计表下标搞错
比如最小值是1，数字3应该存在 3-1=2 的位置，而不是直接 3。新手容易直接拿数字当下标，导致索引越界或统计错误。
输出时忘了加回最小值
从统计表输出时，实际数字是 i + min_val，而不是直接 i。如果最小值是6，i=0 对应数字6，i=1对应7……忘了加回去就会得到0、1、2……完全乱套。
数组里有负数怎么办？
计数排序默认支持负数！只要把 num - min_val 作为下标即可。比如数组 [-3, 0, 2]，最小值是-3，最大值是2，范围大小是 2 - (-3) + 1 = 6。数字-3的下标是 -3 - (-3) = 0，数字0的下标是 0 - (-3) = 3，数字2的下标是 2 - (-3) = 5。完全没问题。
数组里出现了非整数（比如小数）
计数排序只能用于整数，因为我们需要用整数做下标。如果有小数，就不能直接用计数排序。你可以考虑先取整，或者换其他排序算法。

优缺点分析

优点	缺点
速度极快：当数字范围不大时，时间复杂度是 O(n + k)，其中 k 是范围大小。比冒泡、选择排序快得多，甚至比快速排序在某些场景下还快。	浪费内存：如果数字范围很大（比如从1到1亿），统计表会非常大，可能几个G，普通电脑扛不住。
稳定：计数排序是稳定的排序算法（相同数字的相对顺序保持不变，虽然我们这里没体现）。	只能排整数（虽然改造后也可以排负数，但不能是小数）。
简单易懂：思路就像整理积木，小学生也能理解。	不适合数据很分散的情况。
适合给10万以内的小范围正整数排序（比如考试成绩、年龄、编号）。	需要额外的辅助数组空间。

完整可运行代码示例

下面是一个完整的 Python 程序，包含一个成绩排序的实际例子：

def counting_sort(arr):
    """
    对整数数组进行计数排序（支持负数）
    :param arr: 待排序列表
    :return: 排序后的新列表
    """
    if not arr:
        return arr
    
    min_val = min(arr)              # 找最小值
    max_val = max(arr)              # 找最大值
    range_len = max_val - min_val + 1   # 统计表大小
    
    count = [0] * range_len         # 统计表初值为0
    
    # 统计每个数的出现次数
    for num in arr:
        idx = num - min_val
        count[idx] += 1
    
    # 构建结果
    result = []
    for i in range(range_len):
        real_num = i + min_val          # 还原实际数字
        result.extend([real_num] * count[i])
    return result

# ================= 测试场景1：普通整数 =================
scores = [88, 72, 95, 60, 88, 72, 100, 45]
print("原始成绩:", scores)
print("排序后  :", counting_sort(scores))

# ================= 测试场景2：包含负数 =================
temps = [-5, 3, -1, 0, -5, 10, 3]
print("\n气温数据:", temps)
print("排序后  :", counting_sort(temps))

# ================= 测试场景3：空列表 =================
empty = []
print("\n空列表排序:", counting_sort(empty))

输出结果：

原始成绩: [88, 72, 95, 60, 88, 72, 100, 45]
排序后  : [45, 60, 72, 72, 88, 88, 95, 100]

气温数据: [-5, 3, -1, 0, -5, 10, 3]
排序后  : [-5, -5, -1, 0, 3, 3, 10]

空列表排序: []

小练习

请用计数排序给班级数学考试成绩（0~100整数）排个序，比如：[85, 92, 78, 90, 85, 100, 60, 72]。
思考：如果成绩不是整数，而是带小数的（如85.5分），还能用计数排序吗？为什么？
进阶题：请将上面的计数排序改造成“稳定版本”（提示：先计算累积计数，然后从原数组末尾往前遍历，把每个数放到目标位置，同时将对应计数减1）。