- 计数中
- 刚移动
- 已就位
计数排序
当值是范围较小的整数时,计数排序就能派上用场。它为每个可能的值设一个计数器,统计每个值出现的次数,再根据这些计数准确知道每个值该放在哪里。观看读取列表时计数器逐渐增加,再随着每个值移入自己的区段而逐一减少,一次一步。 按“播放”观看排序过程,或用“单步”和“后退”一次走一步。拖动步骤滑块可跳到任意位置。列表和缓冲行之间的长条为每个值放一个计数器。卡片统计已计数的值、移动次数和计数器个数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择柱子数量和初始顺序,或输入自己的整数。试试少量不同值的列表。
- 按“播放”,或用“单步”和“后退”一次移动一个值。拖动步骤滑块可跳到排序的任意位置。
- 观察计数器:读取列表时它们逐渐增加,放置每个值时再逐一减少。
计数排序的原理
为从最小值到最大值的每个值各设一个计数器。读一遍列表,每看到一个值,就把它的计数器加一。然后从最小值开始累加计数:一个值的区段紧接在所有更小的值之后开始。最后再读一遍列表,把每个值移到所在区段的下一个空位,再把结果复制回去。
范围小时很快
计数排序读两遍列表、过一遍计数器,所以工作量随 n + k 增长:值的个数加上计数器的个数。对于小范围内的大量值,比如 0 到 100 的考试分数或年龄,它胜过任何比较排序。范围很大时,它会把时间和内存浪费在没人用的计数器上:分布在 1 到 1,000,000 之间的三个值就需要一百万个计数器。它也是基数排序对每一位重复执行的步骤。
常见问题
计数排序是怎样工作的?
它统计每个值出现的次数,累加计数,找出每个值的区段从哪里开始,然后把每个值直接移到所在区段的下一个空位。它从不比较两个值。
什么时候该用计数排序?
当值是整数(或能转换成整数),而且从最小到最大的范围不比值的个数大太多时,比如成绩、年龄、小编号。这时所需时间与 n + k 成正比。
计数排序稳定吗?
稳定,只要像这里一样按列表顺序把值移到所在区段的下一个空位。正因如此,基数排序才能对每一位使用它。
为什么不直接把每个值按计数的次数写出来?
对单纯的数字来说可以,而且更简单。但真实数据通常不只有键,比如每个分数都附带一个名字,只写出计数的键就会丢掉这些信息。移动元素本身,附带的内容都能保留。
我的数字会被发送到别处吗?
不会。排序在你的浏览器中运行,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器