《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其中所有元素都是非负整数。整体流程可以概括为三步扫描数组求出最大值 m据此创建长度为 m 1 的辅助计数数组counter用counter统计nums中每个数值的出现次数其中counter[num]就是数值num的出现次数统计方式为遍历nums每遇到一个num就将counter[num]加 1由于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这段代码实现得非常直观第一步用一个「擂台式」循环求最大值 mPython 中也可直接写作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_{j0}^i \text{counter[j]} $$前缀和拥有明确的语义prefix[num] - 1正好是数值num在结果数组res中最后一次出现的下标。有了它每个元素应当落在结果数组的哪个位置就一目了然。接下来逆序遍历原数组nums对每个元素num在每次迭代中执行两个动作将num存入结果数组res的下标prefix[num] - 1处把前缀和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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
