企业官网建设流程全解析

《Hello 算法》计数排序（Counting Sort）完全指南：从非负整数到稳定排序的实现原理

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

计数排序（Counting Sort）是一种不依赖元素比较、而是通过统计元素出现次数来完成排序的线性时间算法，通常应用于整数数组。本篇以《Hello 算法》日文版计数排序章节为骨架，结合仓库中 Python 参考实现 与 C 参考实现 的源码级证据，完整讲解「简单实现」与「稳定完全实现」两条演进路径，并给出时间复杂度、空间复杂度、稳定性结论以及严格的适用边界。读完本文，你将能够独立推导前缀和技巧为何能处理「对象排序」，并能在 O(n + m) 时间内写出可排序对象且保持稳定性的计数排序。

计数排序的核心思想：用下标天然排序

与冒泡、快速、归并等基于「两两比较」的算法不同，计数排序走的是另一条路：既然数组下标本身是有序的，那么把每个数出现的次数记下来，再按下标顺序写回，就自然得到了有序结果。

它的适用前提比较明确：给定长度为 n 的数组nums，其中所有元素都是非负整数。整体流程可以概括为三步：

1. 扫描数组求出最大值 m，据此创建长度为 m + 1 的辅助计数数组counter；
2. 用counter统计nums中每个数值的出现次数，其中counter[num]就是数值num的出现次数，统计方式为遍历nums，每遇到一个num就将counter[num]加 1；
3. 由于counter的每个下标天然有序，所有数值已经相当于处于有序状态，此时只需遍历counter，按各数值出现次数由小到大写回nums即可。

下图（位于 ja/docs/chapter_sorting/counting_sort.assets）展示了这一整体流程：

与桶排序的关系：从桶排序的视角看，计数数组counter的每一个下标都可以视作一个「桶」，而计数过程就是把每个元素分发到对应桶里的操作。从本质上讲，计数排序是整数数据场景下桶排序的一个特殊实例。

第一步实现：counting_sort_naive

日文版文档把最初的实现称为「単純な実装」（简单实现），它只能对纯数值数组排序、无法排序对象。下面是文档内嵌 Python Tutor 代码（同步维护于 ja/codes/python/chapter_sorting/counting_sort.py，根目录同名源文件 亦含完全一致的函数）：

def counting_sort_naive(nums: list[int]): """计数排序""" # 简单实现，无法用于排序对象 # 1. 统计数组最大元素 m m = 0 for num in nums: m = max(m, num) # 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

这段代码实现得非常直观：

• 第一步用一个「擂台式」循环求最大值 m（Python 中也可直接写作m = max(nums)）；
• 第二步构造长度 m + 1、初值为 0 的counter，并扫描nums累加次数；
• 第三步双重循环：外层for num in range(m + 1)保证按数值升序输出，内层按counter[num]重复写回num次。

驱动程序使用测试数据nums = [1, 0, 1, 2, 0, 4, 0, 2, 2, 4]（见 counting_sort.py 中的Driver Code），排序完成后打印结果为：

计数排序（无法排序对象）完成后 nums = [0, 0, 0, 1, 1, 2, 2, 2, 4, 4]

这里需要先手动展开编码再调用第 3 步，代价是丢失了各元素原本的身份——这正是下一节「完全实现」要解决的问题。

从「计数」到「定位」：完全实现的稳定版本

细心的读者会发现一个严重缺陷：当输入数据是对象时，上述简单实现无法工作。以商品对象为例，若想按商品价格（成员变量）排序，上面算法只能返回一串排好序的价格数字，根本得不到这些商品本身的有序排列。

那么，如何拿到原数据的排序结果？关键技巧是计算counter的「累積和」（前缀和）。按定义，下标 i 处的前缀和prefix[i]等于数组从开头到第 i 个元素的和：

$$ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} $$

前缀和拥有明确的语义：prefix[num] - 1正好是数值num在结果数组res中最后一次出现的下标。有了它，每个元素应当落在结果数组的哪个位置就一目了然。接下来逆序遍历原数组nums，对每个元素num在每次迭代中执行两个动作：

1. 将num存入结果数组res的下标prefix[num] - 1处；
2. 把前缀和prefix[num]减 1，从而得到下一个num应放置的位置。

遍历结束后，res中即存放了有序结果，最后用res覆盖原数组nums即可。日文版文档用 8 张分步示意图（counting_sort_step1.png 至 counting_sort_step8.png，位于counting_sort.assets目录）完整演示了该过程。

对应的完整实现代码（日文版文档称其为「完全版」，支持排序对象且是稳定排序）如下：

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]

逐个步骤拆解其原理：

• 第 1 步：m = max(nums)求最大值，若需更贴近朴素实现也可手写循环；
• 第 2 步：与简单实现相同，构造counter并统计出现次数；
• 第 3 步：for i in range(m): counter[i + 1] += counter[i]，原地把「出现次数」数组改写成「前缀和」数组，此时counter[num] - 1表示num在res中可放置的最后一个（最靠右的）下标；
• 第 4 步：逆序扫描nums，将每个num放到res[counter[num] - 1]，并立即counter[num] -= 1以腾出下一个空位。由于相同的num总是先取右侧下标再取左侧下标，逆序扫描保证了重复元素在结果中的相对顺序与输入一致，这正是稳定性的来源。

算法特性：复杂度与稳定性

日文版文档在「アルゴリズムの特性」一节给出三条明确结论，这也是面试与工程选型中最常被追问的点：

• 时间复杂度 O(n + m)，且属于非自适应排序：全程只包含对nums的线性扫描与对counter的线性扫描，两层都是线性时间；在通常满足 n ≫ m 时，时间复杂度趋近于 O(n)。复杂度与输入数据的初始有序程度无关，故为非自适应排序。
• 空间复杂度 O(n + m)，属于非原地排序：需要使用长度分别为 n 与 m 的结果数组res与计数数组counter两份额外空间。
• 稳定排序：因为向res填充元素时采用「从右到左」的顺序，逆序遍历nums能够防止相等元素的相对位置被打乱。反过来说，若改成正序遍历nums，虽然仍能得到正确的排序结果，但该结果不再具备稳定性。

严格的使用约束：什么时候该用计数排序

读到此处你可能觉得计数排序异常巧妙，仅靠「数数」就能高效完成排序。但它的前提条件其实相当苛刻，日文版文档在「制約」一节明确指出两点：

• 计数排序只能应用于非负整数。若想用于其他类型的数据，必须保证能够把这些数据转换成非负整数，且转换过程中元素间的相对大小关系保持不变。例如对含负数的整数数组，一个常用做法是给所有元素统一加上一个常数使其全部转为正数，排序完成后再把常数减回去。
• 计数排序适合「数据量大、值域小」的场景。以上面的例子来说，m 不能过大，否则counter会消耗过多空间；并且当 n ≪ m 时，计数排序仍要付出 O(m) 的时间，此时甚至可能比 O(n log n) 的比较类排序算法更慢。

仓库内的跨语言实现与可视化验证

《Hello 算法》在每种支持语言的chapter_sorting目录中都提供了与上述逻辑一一对应的实现。以 C 语言的 counting_sort.c 为例，可以看出它与 Python 版完全同构，只是在细节上更贴近底层：

• 朴素版countingSortNaive与完全版countingSort均先用擂台循环求最大值 m，再用calloc申请counter数组（区别在于完全版后续还要做前缀和与倒序填充）；
• 完全版额外分配res，逆序填充后通过memcpy(nums, res, size * sizeof(int))覆盖原数组，并在函数结束前依次free(res)、free(counter)释放堆内存；
• 两个版本的main驱动函数都使用同一组测试数据[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]调用并打印结果，可用于直接运行验证输出。

这种「文档讲解 + 多语言同构实现」的配套结构，使读者可以在任何语言环境中对照验证算法行为。此外，日文版在 ja/codes/pythontutor/chapter_sorting/counting_sort.md 中为两个版本各内嵌了一条指向 Python Tutor 的交互式执行链接（一个标注counting_sort_naive、一个标注counting_sort），便于逐步观察每一行的状态变化。仓库中同目录下的 bubble_sort.md、merge_sort.md、quick_sort.md 等文件，也以同样的方式覆盖了其余排序算法，方便在统一的框架下横向对比各排序算法的执行轨迹。

小结

计数排序用一个有序的计数数组换掉了比较操作，从而在整数、值域较小的场景下把复杂度压到线性级别。它给我们最重要的两点启发是：其一，数组下标本身就是一种天然的序，很多问题可以借助它免去比较；其二，「前缀和」能把「出现次数」翻译成「目标下标」，配合逆序遍历即可让排序同时具备稳定性——这也是计数排序能作为基数排序内部子过程的原因所在。当你遇到「大量整数、范围不大」的排序诉求时，不妨先想想计数排序；而当数据是宽范围整数、浮点数或对象时，则应回到归并排序、快速排序等通用方案。

如果你想继续深入研究，可以参考同一章节的 基数排序（它在内部多次调用计数排序）以及 桶排序（计数排序可视为其整数特例），并在仓库各语言codes/<语言>/chapter_sorting/counting_sort.*源文件中动手运行验证。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo