hello-algo 计数排序源码解析：从简单计数到稳定排序的完整实现

计数排序（counting sort）是一种通过统计元素出现次数来完成的非比较排序算法。本篇基于 hello-algo 仓库中 counting_sort.py 的 Python 源码，讲解 counting_sort_naive（简单实现）与 counting_sort（完整实现）两套算法的逐行细节、前缀和的“尾索引”转换技巧与稳定性保证，并给出算法特性、局限性及它在基数排序中的实际应用，帮助你在 n 远大于数据范围 m 的场景下选对线性时间排序方案。

一、核心思想：把排序转化为“数数”

计数排序通常应用于整数数组，其整体流程可以概括为三步（以输入为“非负整数”的数组 nums 为例）：

1. 找出最大数字 m：遍历数组，记录最大元素 m，然后创建一个长度为 m + 1 的辅助数组 counter；
2. 统计出现次数：借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法只需遍历 nums（设当前数字为 num），每轮将 counter[num] 加 1 即可；
3. 按索引回填：由于 counter 的各个索引天然有序，相当于所有数字已经“排好序”了。遍历 counter，按各数字出现次数从小到大的顺序把它们填回 nums 即可。

从桶排序的角度看，可以把计数数组 counter 的每个索引视为一个桶，把统计数量的过程看作将各元素分配到对应桶中。本质上，计数排序是桶排序在整型数据下的一个特例——每个“桶”恰好只对应一个整数值，桶内自然有序，无需再做桶内排序。仓库中 bucket_sort.py 给出了通用桶排序的实现（先分桶、桶内排序、再合并），两者对比可以更直观地理解这种特例关系。

二、简单实现 counting_sort_naive 逐行解析

对应源码见 counting_sort.py#L8-L23：

def counting_sort_naive(nums: list[int]):
    """计数排序"""
    # 简单实现，无法用于排序对象
    # 1. 统计数组最大元素 m
    m = max(nums)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 遍历 counter ，将各元素填入原数组 nums
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1

逐行说明：

• 第 12 行 m = max(nums)：一次线性扫描确定数据上界。注意此处隐含一个前提——nums 非空且元素为非负整数，否则 max 会抛异常或 counter[num] 会越界，这正是后文“局限性”一节讨论的边界条件；
• 第 15 行 counter = [0] * (m + 1)：数组大小由 m + 1 决定，这就是计数排序空间开销 O(m) 的来源。当 m 很大而 n 很小时，这一步会成为明显的空间浪费；
• 第 16-17 行计数：counter 下标直接当数值使用（counter[num]），这是“数组充当哈希表”的典型用法，时间复杂度为 O(n)；
• 第 19-23 行回填：外层按 num 从小到大遍历，内层重复 counter[num] 次把 num 写入 nums[i]。总写入次数恰好等于 n。

仓库中同一逻辑的多语言实现可交叉印证：Java 版本见 counting_sort.java#L14-L33，C 语言版本（用 calloc 分配、free 释放计数数组）见 counting_sort.c#L11-L34。

驱动代码验证：counting_sort.py#L53-L58 使用测试数组：

nums = [1, 0, 1, 2, 0, 4, 0, 2, 2, 4]
counting_sort_naive(nums)
# 输出：计数排序（无法排序对象）完成后 nums = [0, 0, 0, 1, 1, 2, 2, 2, 4, 4]

在本地运行 python codes/python/chapter_sorting/counting_sort.py 即可复现。

三、简单实现为何“无法排序对象”

简单实现的第 3 步存在一个致命缺陷：回填时丢弃了原始元素的身份。假设输入是一批商品对象，想按价格（类的某个成员变量）排序，简单实现只能得到“价格的排序结果”，而丢失了各价格对应的商品本身。

问题出在：counter 只记录了“值”的频次，回填时是按值重新生成的，无法区分两个同值元素的原始先后顺序，更无法把对象映射回去。要解决这个问题，需要知道每个元素应该放进结果数组的哪个具体位置——这就是前缀和登场的原因。

四、完整实现 counting_sort：前缀和 + 倒序回填

对应源码见 counting_sort.py#L26-L50：

def counting_sort(nums: list[int]):
    """计数排序"""
    # 完整实现，可排序对象，并且是稳定排序
    # 1. 统计数组最大元素 m
    m = max(nums)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
    # 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i in range(m):
        counter[i + 1] += counter[i]
    # 4. 倒序遍历 nums ，将各元素填入结果数组 res
    # 初始化数组 res 用于记录结果
    n = len(nums)
    res = [0] * n
    for i in range(n - 1, -1, -1):
        num = nums[i]
        res[counter[num] - 1] = num  # 将 num 放置到对应索引处
        counter[num] -= 1  # 令前缀和自减 1 ，得到下次放置 num 的索引
    # 使用结果数组 res 覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]

4.1 前缀和：把“出现次数”转换为“尾索引”

前第 3 步（第 38-39 行）计算 counter 的前缀和。前缀和的定义是：索引 i 处的 prefix[i] 等于数组前 i 个元素之和，即：

prefix[i] = counter[0] + counter[1] + ... + counter[i]

前缀和具有明确的意义：counter[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。 直觉上：所有严格小于 num 的数字一共有 counter[num] - counter[num]（即前缀和减去本位计数）个，它们排在 num 之前，因此 num 的最后一个位置就是 counter[num] - 1。

以驱动数组 [1, 0, 1, 2, 0, 4, 0, 2, 2, 4] 为例：计数后 counter = [3, 2, 3, 0, 2]，前缀和后 counter = [3, 5, 8, 8, 10]，含义变为——数字 0 占 res 的 [0, 2]、1 占 [3, 4]、2 占 [5, 7]、4 占 [8, 9]，各数字的“尾索引”一目了然。

实现细节：第 38 行 for i in range(m) 只迭代到 m - 1，因为循环体访问的是 counter[i + 1]，最后一个需要累加的位置是 counter[m]。Java 实现 与 C 实现 采用完全一致的边界处理。

4.2 倒序遍历保证稳定性

第 4 步（第 44-47 行）是完整实现的关键，每轮迭代执行两步：

1. 将 num 填入 res 的索引 counter[num] - 1 处；
2. 令 counter[num] 减 1，得到下次放置 num 的索引。

为什么必须“倒序”遍历 nums？ 假设 res 中待填的两个相同值 num 分别来自原数组索引 i < j 的两处。倒序遍历时先处理 j：它占据 num 的尾索引（较靠右的位置）；随后处理 i：counter[num] 已减 1，i 处的元素落到左侧位置。结果中 i 仍然排在 j 前面——相等元素的相对顺序与输入一致，排序因此是稳定的。

反过来，若正序遍历，后出现的同值元素会先抢占左侧位置，相对顺序被颠倒，结果虽然仍然有序但不稳定。这一结论也可以从 counting_sort_digit 得到印证：它同样采用“前缀和 + 倒序回填”的模板，因为基数排序依赖每一轮按位计数排序的稳定性来保持高位已确定的顺序。

第 49-50 行最后把 res 逐位复制回 nums，与 C 语言版本使用 memcpy 一次性覆盖（见 counting_sort.c#L66）效果等价，都是为了让“原地排序”的调用接口保持一致。

稳定性的对象化价值：由于每个元素都通过“尾索引”被放置到唯一确定的位置，把 num 换成“键函数（如商品价格）”即可把对象本身填入 res，这正是完整实现可排序对象的原因——它记录的是位置而非值。

五、算法特性

特性	结论	依据
时间复杂度	O(n + m)，非自适应	遍历 nums 与遍历 counter 均为线性；n 远大于 m 时趋于 O(n)
空间复杂度	O(n + m)，非原地	需要长度 n 的 res 与长度 m + 1 的 counter（见第 33、43 行）
稳定性	稳定排序	向 res 填充元素从右向左进行，倒序遍历避免改变相等元素相对位置

与常见比较排序（O(n log n)）相比，计数排序的线性复杂度优势只在 m 与 n 同数量级或更小时成立。

六、局限性与适用边界

1. 只适用于非负整数。 若数据不是非负整数，需要先保证“可转换为非负整数且转换不改变元素间相对大小关系”。例如含负数的整数数组，可以先给所有数字加上一个常数（如减去最小值）平移为非负数，排序完成后再转换回去。这也解释了为何源码第 15 行直接用 counter[num] 按下标访问而无需任何判负——仓库实现假定输入已满足前提，属于调用方契约而非算法自带能力。

2. 适用于“数据量大但数据范围较小”的场景。 上例中若 m 过大，长度为 m + 1 的 counter 会占用过多空间；而当 n 远小于 m 时，计数排序花费 O(m) 时间，可能比 O(n log n) 的比较排序还慢。选型时可以按以下经验判断：

• m = O(n)（值域与规模同阶）：计数排序优于通用比较排序；
• m 远小于 n（如统计年龄段、打分）：计数排序优势最明显；
• m 远大于 n（如 64 位随机整数）：应改用基数排序或比较排序。

3. 在基数排序中，值域被天然压缩。 radix_sort.py 中按位计数排序时，十进制的“值域”恒为 0~9，因此桶数组固定为 counter = [0] * 10，第 24-25 行的前缀和也只需 range(1, 10)。这展示了完整实现模板（前缀和 + 倒序回填）的复用价值：计数排序既可作为独立算法，也可作为基数排序按位排序的内核，每一轮的稳定性正是整体正确性的基石。

七、参考路径与运行方式

• Python 实现（本文主源码）：counting_sort.py，直接 python codes/python/chapter_sorting/counting_sort.py 即可运行驱动代码；
• 同构多语言实现：Java 版本、C 版本，countingSortNaive / countingSort 与 Python 的两函数一一对应；
• 关联算法：bucket_sort.py（计数排序是其整型特例）、radix_sort.py（以稳定计数排序为按位内核）；
• 教程图解文档：docs/chapter_sorting/counting_sort.md，其中 counting_sort_step1.png 至 counting_sort_step8.png 提供了完整实现的逐步动画图解。