2

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

直观地，您可以按数字的最高位对数字进行排序，递归地对每个生成的 bin 进行排序，然后按顺序组合这些牌组。不幸的是，由于必须将 10 个垃圾箱中的 9 个垃圾箱中的卡片放在一边以便对每个垃圾箱进行分类，因此此过程会生成许多中间卡片堆，您必须对其进行跟踪。

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

4

2 回答 2

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

  • 不需要按最低有效位（1 位）排序，因为没有十个桶有多个数字。但是，一百个桶并非如此（练习：自己递归排序）。因此，将现在排序的零百桶连接起来，按顺序连接，与一、三和八百桶一起给出：

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

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

于 2012-10-15T06:02:22.317 回答
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（与其他专家程序员一样）不喜欢在必要时做繁琐的工作。

于 2012-10-15T09:07:59.463 回答