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

Question

我正在阅读Cormen等人的算法导论。人。而且在它们所描述的基数排序的一部分，他们说：

直觉，你可能会在自己最显著位数排序，每个递归所产生箱，然后 排序结合甲板 秩序。不幸的是，由于10个垃圾箱中有9个垃圾箱的卡片必须是 ，因此需要对每个垃圾箱进行分类，此过程会生成许多卡片，您必须对其进行跟踪。

这是什么意思？ 我不明白如何按MSB排序会是一个问题？

Answer 1

它们指的是LSD基数排序的有用属性，既然你确保每个排序步骤是稳定，你只需要对整个数组上的每个数字运行一个步骤，而且你不必单独对任何子集进行排序。

采取迈克尔的示例性数据：

后0步骤：

170，045，075，090，002，024，802，066，182，332，140，144

后1个步骤（排序上单位）：

170，090，140，002，802，182，332，024，144，045，075，066

后2个步骤（上几十排序）：

002，802，024，332，140，144，045，066，170，075，182，090

后3个步骤（排序在数百）：

002，024，045，066 ，075,090,140,​​144,170,182,332,802

如果你在二进制中进行基数排序而不是基于10，那么这个属性就变得特别有用。然后每个排序步骤只是一个分为两部分的分区，这很简单。至少，直到你想要做，而不使用任何额外的内存。

MSD基数排序的工作，当然，它只是需要更多的簿记和/或非尾递归。这只是一个“问题”，因为CLRS（与其他专家程序员一样）不喜欢在必要之前进行繁琐的工作。

Answer 2

考虑下面的示例列表进行排序： 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

• 由至少排序显著位（1S地方）是不需要的，因为没有几十桶不止一个号码。尽管如此，这不是这种情况（练习：自己递归排序）。因此，现在分类零个数百桶拼接，加入顺序，与一，三，八数百桶给：

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

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