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
  • 40 岁:045
  • 六十年代:066
  • 七十年代:075
  • 九十年代:090

• 不需要按最低有效位(第 1 位)排序，因为没有超过一个数字的十位桶。但是，一百个桶不是这种情况(练习:自己递归排序)。因此，将现在排序的零百桶连接起来，按顺序与一、三和八百桶进行连接，得到:

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

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