algorithm - 为什么不应该从 MSD 开始实现基数排序？

Question

我正在阅读 Cormen 等人的《算法简介》。等人。在他们描述基数排序的部分，他们说:

Intuitively you might sort numbers on their most significant digit, sort each of the resulting bins recursively and then combine the decks in order. Unfortunately since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that you'd have to keep a track of.

这是什么意思？ 我不明白按 MSB 排序会出现问题吗？

Answer 1

考虑以下示例列表进行排序: 170、045、075、090、002、024、802、066、182、332、140、144

• 按最高有效数字(百位)排序得出:

  • 零百桶:045、075、090、002、024、066

  • 一百个桶:170、182、140、144

  • 三百桶:332

  • 八百桶:802

• 现在需要对零和百存储桶中的数字按下一位进行排序(其他两个存储桶各只包含一项):

  • 零十:002
  • 二十岁:024
  • 四十岁:045
  • 六十年代:066
  • 七十年代:075
  • 九十年代:090

• 不需要按最低有效数字(1 位)排序，因为不存在包含多个数字的十位桶。不过，一百个桶的情况并非如此(练习:自己递归排序)。因此，现在已排序的零百桶将按顺序连接起来，与一、三和八百桶相连接，得到:

  002、024、045、066、075、090、140、144、170、182、332、801

您可以看到作者指的是中间递归排序步骤，这在 LSD 基数排序中不是必需的。