- 使用中的桶
- 刚移动
- 已复制回
- 已就位
基数排序
基数排序给整数排序,却从不比较其中任何两个。它先按个位排序列表,再按十位,再按百位,每次都把值移入十个桶,再按顺序复制回来。在列表下方的一行中观看桶一步步填满,看列表按越来越多的数位排好。 按“播放”观看排序过程,或用“单步”和“后退”逐次移动。拖动步骤滑块可跳到任意位置。列表下方的一行中并排放着 0 到 9 号桶。卡片统计读取的数位、移动次数和趟数。可选择柱子数量、初始顺序,或输入自己的数字(最大 999)。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择柱子数量和初始顺序,或输入自己的整数(最大 999),观看百位那一趟。
- 按“播放”,或用“单步”和“后退”逐个移动值。拖动步骤滑块可跳到排序的任意位置。
- 观察每一趟:统计数位,把每个值移入它的桶,再把桶复制回来。
基数排序的原理
只看每个数的最后一位,并按它排序列表:把每个数放入 0 到 9 这十个桶之一,保持它们到来的顺序,然后把桶依次复制回来。再对十位、百位做同样的事。由于每一趟都保持同一数字的数的原有顺序,前面几趟仍决定着它们之间的顺序,最后一趟之后整个列表就排好了。
完全不比较
比较排序无论用什么巧妙的技巧,最坏情况下都至少需要约 n log₂ n 次比较。基数排序改为读取数位,绕开了这个下限:每一趟读取每个值的一位数字,并把每个值移动两次,所以 d 位数字需要 d 趟,工作量随 n · d 增长。对于由短键组成的长列表,这很划算:一百万个不超过 999 的数只需三趟,而比较排序约需 2000 万次比较。代价是它只适用于由数字或字符组成的键,并且需要存放桶的空间。
常见问题
基数排序是怎样工作的?
它先按最后一位排序这些数,再按前一位,依次直到第一位。每一趟按该位数字把数放入十个桶,保持顺序,再把桶复制回来。完成最高位那一趟后,列表就排好了。
为什么从最后一位开始?
因为每一趟都是稳定的:同一数字的数保持前几趟给出的顺序。所以按第一位进行的最后一趟决定顺序,相同时由已经排好的数位决定先后。这叫 LSD(最低有效位)基数排序。
基数排序比快速排序快吗?
对于大量短键,可能更快:它的工作量随值的个数乘以位数增长,没有 n log n。对于少量值、很长的键,或不是由数字组成的数据,快速排序和归并排序通常更快也更简单。
它和计数排序有什么关系?
基数排序的每一趟都是对一位数字的计数排序:统计每个数字各有多少个值,算出每个桶的起点,再按顺序把值移过去。
我的数字会被发送到别处吗?
不会。排序在你的浏览器中运行,你上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器