基数排序

基数排序在排序算法中是个异类:它从不问两个值哪个更大。它逐位读取数字,每次按一位排序,用的是十个桶。这个想法比计算机还古老:穿孔卡片分类机就是这样工作的。

列表的柱子位于一行标有 0 到 9 的十个桶上方,一个值正落入其最后一位对应的桶
列表的柱子位于一行标有 0 到 9 的十个桶上方,一个值正落入其最后一位对应的桶

基本思路

先只按个位排序这些数。再按十位排序,但要让十位相同的数保持第一趟给出的顺序。然后用同样的方法按百位排序。最后一趟之后列表就排好了:百位先决定顺序,百位相同的已按十位排好,十位也相同的已按个位排好。

用桶完成一趟

每一趟用十个桶,每个数字 0 到 9 一个。从头到尾遍历列表,把每个数移入其数字对应的桶,排在桶里已有的数后面。然后按顺序把桶倒回列表,先倒 0 号桶。按列表顺序移动、并追加到桶的末尾,正是这一趟保持稳定的原因。本应用会先统计每个数字的个数,这样桶就能在一行中并排放置,每个桶紧接在前一个之后开始:这就是对一位数字的计数排序。

一个例子

取 170, 45, 75, 90, 802, 24, 2, 66。按个位:170, 90, 802, 2, 24, 45, 75, 66。按十位:802, 2, 24, 45, 66, 170, 75, 90;注意 802 和 2 的十位都是 0,它们保持第一趟的顺序。按百位:2, 24, 45, 66, 75, 90, 170, 802。对八个数进行三趟:读取 24 个数位,移动 48 次,没有一次比较。

有多快?

每一趟读取每个数的一位数字,并把每个数移动两次,所以对于 n 个 d 位数,工作量随 n · d 增长。比较排序在最坏情况下至少需要约 n log₂ n 次比较,因为它必须靠一个个是非问题区分 n! 种可能的顺序。基数排序不受此限制,因为它从不问这样的问题。对于大量短键,比如一百万个小于 1,000 的数,三趟的工作量远小于比较排序所需的约 2000 万次比较。对于长键或少量值,这一优势就消失了。

LSD 与 MSD,以及历史

这里展示的版本从最低有效位(LSD)开始。反过来,从最高有效位开始(MSD),会按第一位把列表分到各个桶中,再分别排序每个桶,适合长度不同的字符串。基数排序可以追溯到穿孔卡片分类机,它们出现在 Herman Hollerith 为 1890 年美国人口普查制造的制表机之后:分类机根据某一列上的孔把每张卡片放入十个格子之一,操作员每一列让整叠卡片过一遍,从最后一列开始。

计算机历史博物馆中的一台霍勒里斯穿孔卡片制表机,与1890年美国人口普查所用的同类。操作员按列把一叠卡片各过一遍分类机,这是基数排序的前身。
计算机历史博物馆中的一台霍勒里斯穿孔卡片制表机,与1890年美国人口普查所用的同类。操作员按列把一叠卡片各过一遍分类机,这是基数排序的前身。

动手试试

打开应用并按“单步”。每一趟先统计数位,在列表下方的一行中划出 0 到 9 号桶。然后数字逐个落入各自的桶,当前桶高亮显示,再被复制回来。输入自己的数字(最大 999),比如上面的例子,即可看到全部三趟。

常见问题

基数排序的时间复杂度是多少?

对于固定基数下 n 个 d 位的键,是 O(n · d),外加每一趟桶的开销。它需要 O(n) 的额外内存,用作存放桶的缓冲区。

基数排序稳定吗?

LSD 基数排序必须稳定:它之所以有效,正是因为每一趟都让同一数字的值保持进来时的顺序。因此最终结果也是稳定的。

基数排序能处理负数或小数吗?

不能直接处理,但可以借助技巧:把负数平移,使它们都变成正数;或者把负数单独排序再反转。浮点数经过一个小变换后,可以按其位模式排序。

为什么用十进制?

因为容易理解。计算机通常每次按 8 或 16 个二进制位排序,所以一个 32 位的数需要四趟或两趟,对应 256 或 65,536 个桶。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试基数排序