尧图网页设计 
Hello 算法计数排序的完整实现、稳定性原理与适用边界详解【免费下载链接】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本篇基于《Hello 算法》仓库中 计数排序章节系统讲解计数排序counting sort的两种实现——面向整数数组的简单实现与可排序对象、且保证稳定的完整实现。读完本文你将掌握计数数组counter的构造流程、前缀和如何把“出现次数”转换为“结果索引”、倒序遍历保证排序稳定性的原理以及计数排序时间复杂度 O(n m) 背后的适用条件与局限性并能直接对照仓库中 Python、Java、C、Go、Rust 等十余种语言的源码逐行验证。算法定义用统计代替比较计数排序counting sort通过统计元素数量来实现排序通常应用于整数数组。与 排序算法章首节 介绍的基于比较的排序不同计数排序属于非比较排序算法不依赖元素间的两两比较因此可以突破比较排序 O(n log n) 的时间下界在数据范围 m 较小时达到线性时间。设输入为长度 n 的数组nums元素均为非负整数最大值为 m算法的核心思想可概括为三步找最大值并建计数数组遍历nums找出最大数字 m创建一个长度为m 1的辅助数组counter统计出现次数遍历nums设当前数字为num每轮将counter[num]增加 1。这样counter[num]就对应数字num的出现次数利用索引天然有序回填由于counter的各个索引0、1、2、…、m天然有序相当于所有数字已经按大小排好了。只需遍历counter把各数字按其出现次数从小到大顺序填入nums即可。计数排序与桶排序的联系从桶排序的角度看可以把计数数组counter的每个索引视为一个桶把统计数量的过程看作将各个元素分配到对应的桶中。本质上计数排序是桶排序在整型数据下的一个特例。仓库中的 桶排序章节 对此有更完整的展开。简单实现counting_sort_naive以 Python 版 counting_sort.py 为例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其他语言的实现与上述 Python 版本一一对应均保持相同的三步结构与中文注释便于跨语言比对counting_sort.pyPythoncounting_sort.javaJavacountingSortNaive方法counting_sort.cppCcountingSortNaive函数counting_sort.goGocountingSortNaive函数counting_sort.rsRustcounting_sort_naive函数各语言驱动代码使用相同的测试数据[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]排序后输出[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]可以直接运行验证例如python codes/python/chapter_sorting/counting_sort.py。完整实现前缀和与稳定排序细心的读者可能发现了如果输入数据是对象上述步骤 3 就失效了。假设输入数据是商品对象我们想按照商品价格类的成员变量对商品进行排序而简单实现只能给出价格的排序结果丢失了元素与键值的对应关系。要得到原数据的排序结果关键一步是计算counter的前缀和。顾名思义索引i处的前缀和prefix[i]等于数组前i 1个元素之和prefix[i] counter[0] counter[1] … counter[i]前缀和具有明确的意义prefix[num] - 1代表元素num在结果数组res中最后一次出现的索引。这个信息非常关键因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来倒序遍历原数组nums的每个元素num在每轮迭代中执行两步将num填入res的索引prefix[num] - 1处令prefix[num]减小 1从而得到下次放置num的索引。遍历完成后res中就是排序好的结果最后用res覆盖原数组nums即可。用示例数据推演一遍仓库驱动代码的输入为nums [1, 0, 1, 2, 0, 4, 0, 2, 2, 4]n 10m 4。统计阶段得到counter [3, 2, 3, 0, 2]即 0 出现 3 次、1 出现 2 次、2 出现 3 次、3 出现 0 次、4 出现 2 次求前缀和后counter [3, 5, 8, 8, 10]。此后倒序遍历nums的完整过程如下迭代 inum放置位置counter[num]-1res 状态949[…, …, …, …, …, …, …, …, …, 4]827[…, …, …, …, …, …, …, 2, …, 4]726[…, …, …, …, …, …, 2, 2, …, 4]602[…, …, 0, …, …, …, 2, 2, …, 4]548[…, …, 0, …, …, …, 2, 2, 4, 4]401[…, 0, 0, …, …, …, 2, 2, 4, 4]325[…, 0, 0, …, …, 2, 2, 2, 4, 4]214[…, 0, 0, …, 1, 2, 2, 2, 4, 4]100[0, 0, 0, …, 1, 2, 2, 2, 4, 4]013[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]最终res [0, 0, 0, 1, 1, 2, 2, 2, 4, 4]与各语言驱动代码的实际输出一致。完整实现源码剖析Python 版 counting_sort.py 中的counting_sort函数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]对照仓库源码有几个实现细节值得注意前缀和的 in-place 计算各语言都在原counter上就地累加如 C 的 counting_sort.cppcounter[i 1] counter[i]没有额外开辟prefix数组。求和后counter的语义从“出现次数”变为“尾索引 1”注释中的“将出现次数转换为尾索引”正是指这一步。覆盖原数组的方式因语言而异从源码结构看Python 逐元素回写、C 直接nums res整体替换、Go 用内置copy(nums, res)见 counting_sort.go、Rust 用nums.copy_from_slice(res)见 counting_sort.rsJava 同样逐元素回写见 counting_sort.java但对调用方的语义完全一致。完整实现可推广到对象排序源码中排序的是整数数组但如各文件注释所言“可排序对象”。原理是把num替换为对象的键值如商品价格res中存放对象本身其余流程不变——这正是简单实现做不到的。算法特性时间复杂度为 O(n m)、非自适应排序涉及遍历nums和遍历counter都使用线性时间。一般情况下 n ≫ m时间复杂度趋于 O(n)。注意它不随输入分布“自适应”变快变慢这与桶排序“桶数量 k 较大时趋向 O(n)”的特性形成对比见 桶排序章节。空间复杂度为 O(n m)、非原地排序借助了长度分别为 n 和 m 的数组res和counter。稳定排序由于向res中填充元素的顺序是“从右向左”的倒序遍历nums可以避免改变相等元素之间的相对位置从而实现稳定排序。实际上正序遍历nums也可以得到正确的排序结果但结果是非稳定的——这是完整实现刻意选择倒序遍历的原因也与上表推演中相等元素如三个 0保持原有先后顺序的现象吻合。局限性与适用边界看到这里你也许会觉得计数排序非常巧妙仅通过统计数量就可以实现高效的排序。然而使用计数排序的前置条件相对较为严格。只适用于非负整数。若想将其用于其他类型的数据需要确保这些数据可以转换为非负整数并且在转换过程中不能改变各个元素之间的相对大小关系。例如对于包含负数的整数数组可以先给所有数字加上一个常数如减去最小值将全部数字转化为非负数排序完成后再转换回去。适用于数据量大但数据范围小的情况。在上述示例中 m 不能太大否则计数数组会占用过多空间而当 n ≪ m 时计数排序使用 O(m) 时间可能比 O(n log n) 的比较排序还要慢。因此选择该算法前应先评估 n 与 m 的比例m 与 n 同量级或更小时优势明显m 远超 n 时不如直接采用比较排序。与基数排序的关系对于超出计数数组可承受范围的大范围整数如 32 位整数可以按位分段统计这正是 基数排序章节 讲的主题——计数排序在其中充当了每一轮按位归桶的底层工具。多语言实现与运行方式计数排序是仓库 codes/ 目录下覆盖语言最全的算法之一chapter_sorting目录在 Python、Java、C、C、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart、Zig 等语言中均有同名文件如 counting_sort.kt、counting_sort.swift且都实现了naive与完整两个版本方便横向对照同一算法在不同语言中的惯用写法。各语言均以相同的测试数组[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]驱动输出排序前后的数组。运行方式以各语言的标准工具链为准Python 可直接执行脚本文件C/C 通过各目录的CMakeLists.txt构建Go 目录下含go.modRust 目录含Cargo.toml可用cargo run运行。小结计数排序展示了非比较排序的典型思路把“排序”转化为“统计 索引映射”。简单实现用 O(m) 的计数数组直接重建数组胜在简洁但无法处理对象完整实现通过前缀和把出现次数转换为尾索引配合从右向左的倒序填充既保留了原数据对应关系又实现了稳定排序。其 O(n m) 的时间与空间开销决定了它最适合“元素为非负整数或可无损映射为非负整数、数据范围 m 相对较小”的场景面对大范围数据时应转向基数排序或桶排序。仓库中十余种语言的逐行对应实现naive版与完整版成对出现为逐语言验证这一流程提供了现成的素材。【免费下载链接】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），仅供参考 Hello 算法：计数排序的完整实现、稳定性原理与适用边界详解
Hello 算法计数排序的完整实现、稳定性原理与适用边界详解【免费下载链接】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本篇基于《Hello 算法》仓库中 计数排序章节系统讲解计数排序counting sort的两种实现——面向整数数组的简单实现与可排序对象、且保证稳定的完整实现。读完本文你将掌握计数数组counter的构造流程、前缀和如何把“出现次数”转换为“结果索引”、倒序遍历保证排序稳定性的原理以及计数排序时间复杂度 O(n m) 背后的适用条件与局限性并能直接对照仓库中 Python、Java、C、Go、Rust 等十余种语言的源码逐行验证。算法定义用统计代替比较计数排序counting sort通过统计元素数量来实现排序通常应用于整数数组。与 排序算法章首节 介绍的基于比较的排序不同计数排序属于非比较排序算法不依赖元素间的两两比较因此可以突破比较排序 O(n log n) 的时间下界在数据范围 m 较小时达到线性时间。设输入为长度 n 的数组nums元素均为非负整数最大值为 m算法的核心思想可概括为三步找最大值并建计数数组遍历nums找出最大数字 m创建一个长度为m 1的辅助数组counter统计出现次数遍历nums设当前数字为num每轮将counter[num]增加 1。这样counter[num]就对应数字num的出现次数利用索引天然有序回填由于counter的各个索引0、1、2、…、m天然有序相当于所有数字已经按大小排好了。只需遍历counter把各数字按其出现次数从小到大顺序填入nums即可。计数排序与桶排序的联系从桶排序的角度看可以把计数数组counter的每个索引视为一个桶把统计数量的过程看作将各个元素分配到对应的桶中。本质上计数排序是桶排序在整型数据下的一个特例。仓库中的 桶排序章节 对此有更完整的展开。简单实现counting_sort_naive以 Python 版 counting_sort.py 为例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其他语言的实现与上述 Python 版本一一对应均保持相同的三步结构与中文注释便于跨语言比对counting_sort.pyPythoncounting_sort.javaJavacountingSortNaive方法counting_sort.cppCcountingSortNaive函数counting_sort.goGocountingSortNaive函数counting_sort.rsRustcounting_sort_naive函数各语言驱动代码使用相同的测试数据[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]排序后输出[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]可以直接运行验证例如python codes/python/chapter_sorting/counting_sort.py。完整实现前缀和与稳定排序细心的读者可能发现了如果输入数据是对象上述步骤 3 就失效了。假设输入数据是商品对象我们想按照商品价格类的成员变量对商品进行排序而简单实现只能给出价格的排序结果丢失了元素与键值的对应关系。要得到原数据的排序结果关键一步是计算counter的前缀和。顾名思义索引i处的前缀和prefix[i]等于数组前i 1个元素之和prefix[i] counter[0] counter[1] … counter[i]前缀和具有明确的意义prefix[num] - 1代表元素num在结果数组res中最后一次出现的索引。这个信息非常关键因为它告诉我们各个元素应该出现在结果数组的哪个位置。接下来倒序遍历原数组nums的每个元素num在每轮迭代中执行两步将num填入res的索引prefix[num] - 1处令prefix[num]减小 1从而得到下次放置num的索引。遍历完成后res中就是排序好的结果最后用res覆盖原数组nums即可。用示例数据推演一遍仓库驱动代码的输入为nums [1, 0, 1, 2, 0, 4, 0, 2, 2, 4]n 10m 4。统计阶段得到counter [3, 2, 3, 0, 2]即 0 出现 3 次、1 出现 2 次、2 出现 3 次、3 出现 0 次、4 出现 2 次求前缀和后counter [3, 5, 8, 8, 10]。此后倒序遍历nums的完整过程如下迭代 inum放置位置counter[num]-1res 状态949[…, …, …, …, …, …, …, …, …, 4]827[…, …, …, …, …, …, …, 2, …, 4]726[…, …, …, …, …, …, 2, 2, …, 4]602[…, …, 0, …, …, …, 2, 2, …, 4]548[…, …, 0, …, …, …, 2, 2, 4, 4]401[…, 0, 0, …, …, …, 2, 2, 4, 4]325[…, 0, 0, …, …, 2, 2, 2, 4, 4]214[…, 0, 0, …, 1, 2, 2, 2, 4, 4]100[0, 0, 0, …, 1, 2, 2, 2, 4, 4]013[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]最终res [0, 0, 0, 1, 1, 2, 2, 2, 4, 4]与各语言驱动代码的实际输出一致。完整实现源码剖析Python 版 counting_sort.py 中的counting_sort函数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]对照仓库源码有几个实现细节值得注意前缀和的 in-place 计算各语言都在原counter上就地累加如 C 的 counting_sort.cppcounter[i 1] counter[i]没有额外开辟prefix数组。求和后counter的语义从“出现次数”变为“尾索引 1”注释中的“将出现次数转换为尾索引”正是指这一步。覆盖原数组的方式因语言而异从源码结构看Python 逐元素回写、C 直接nums res整体替换、Go 用内置copy(nums, res)见 counting_sort.go、Rust 用nums.copy_from_slice(res)见 counting_sort.rsJava 同样逐元素回写见 counting_sort.java但对调用方的语义完全一致。完整实现可推广到对象排序源码中排序的是整数数组但如各文件注释所言“可排序对象”。原理是把num替换为对象的键值如商品价格res中存放对象本身其余流程不变——这正是简单实现做不到的。算法特性时间复杂度为 O(n m)、非自适应排序涉及遍历nums和遍历counter都使用线性时间。一般情况下 n ≫ m时间复杂度趋于 O(n)。注意它不随输入分布“自适应”变快变慢这与桶排序“桶数量 k 较大时趋向 O(n)”的特性形成对比见 桶排序章节。空间复杂度为 O(n m)、非原地排序借助了长度分别为 n 和 m 的数组res和counter。稳定排序由于向res中填充元素的顺序是“从右向左”的倒序遍历nums可以避免改变相等元素之间的相对位置从而实现稳定排序。实际上正序遍历nums也可以得到正确的排序结果但结果是非稳定的——这是完整实现刻意选择倒序遍历的原因也与上表推演中相等元素如三个 0保持原有先后顺序的现象吻合。局限性与适用边界看到这里你也许会觉得计数排序非常巧妙仅通过统计数量就可以实现高效的排序。然而使用计数排序的前置条件相对较为严格。只适用于非负整数。若想将其用于其他类型的数据需要确保这些数据可以转换为非负整数并且在转换过程中不能改变各个元素之间的相对大小关系。例如对于包含负数的整数数组可以先给所有数字加上一个常数如减去最小值将全部数字转化为非负数排序完成后再转换回去。适用于数据量大但数据范围小的情况。在上述示例中 m 不能太大否则计数数组会占用过多空间而当 n ≪ m 时计数排序使用 O(m) 时间可能比 O(n log n) 的比较排序还要慢。因此选择该算法前应先评估 n 与 m 的比例m 与 n 同量级或更小时优势明显m 远超 n 时不如直接采用比较排序。与基数排序的关系对于超出计数数组可承受范围的大范围整数如 32 位整数可以按位分段统计这正是 基数排序章节 讲的主题——计数排序在其中充当了每一轮按位归桶的底层工具。多语言实现与运行方式计数排序是仓库 codes/ 目录下覆盖语言最全的算法之一chapter_sorting目录在 Python、Java、C、C、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart、Zig 等语言中均有同名文件如 counting_sort.kt、counting_sort.swift且都实现了naive与完整两个版本方便横向对照同一算法在不同语言中的惯用写法。各语言均以相同的测试数组[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]驱动输出排序前后的数组。运行方式以各语言的标准工具链为准Python 可直接执行脚本文件C/C 通过各目录的CMakeLists.txt构建Go 目录下含go.modRust 目录含Cargo.toml可用cargo run运行。小结计数排序展示了非比较排序的典型思路把“排序”转化为“统计 索引映射”。简单实现用 O(m) 的计数数组直接重建数组胜在简洁但无法处理对象完整实现通过前缀和把出现次数转换为尾索引配合从右向左的倒序填充既保留了原数据对应关系又实现了稳定排序。其 O(n m) 的时间与空间开销决定了它最适合“元素为非负整数或可无损映射为非负整数、数据范围 m 相对较小”的场景面对大范围数据时应转向基数排序或桶排序。仓库中十余种语言的逐行对应实现naive版与完整版成对出现为逐语言验证这一流程提供了现成的素材。【免费下载链接】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），仅供参考