5

我真的很困惑“就地”MSD基数排序算法：

然后使用下一个数字递归处理每个 bin，直到所有数字都用于排序。

我很困惑，因为在我看来递归意味着 O(n) 堆栈空间，其中n是最长字符串的长度（以位数为单位），对吧？

在我看来，避免堆栈溢出的唯一方法是使用堆空间——但是根据任何定义，该算法不再是“就地”的。

那么，如何就地进行 MSD 基数排序呢？

4

2 回答 2

2

我认为术语“就地 MSD 基数排序”有点误导，因为正如您所指出的，它不是严格定义“就地”的就地算法。这里的“就地”术语很可能是指这样一个事实，与 LSD 基数排序不同，该算法不需要辅助数组来临时存储原始输入数组中的元素。

您是正确的，MSD 基数排序的空间使用量与最大输入数中的位数成正比。为了符号简单，我们让 n 是输入数组的长度，U 是数组中的最大数。MSD 基数排序的运行时间为 O(n log U)，因为数字 U 的位数为 O(log U)。O(log U) 是一个非常非常缓慢增长的函数。作为参考，宇宙中的原子数大约是 10 80，也就是大约 2 240。因此，如果您对任何物理过程生成的数字进行排序，递归深度最多为 240，虽然很大，但绝对是可以管理的。

如果你真的在分类大数字 - 比如说，具有数千位和数千位的数字 - 那么你担心会炸毁堆栈是正确的。但是，我认为如果您有一个良好的 MSD 基数排序实现，这种情况发生的可能性极小。快速排序中有一个标准优化——看起来很像 MSD 基数排序——不是进行两个分支递归调用，而是对两个范围中较小的一个进行递归调用以进行排序，然后将堆栈帧从初始调用回收到排序更大的范围。（这本质上是一个尾调用消除）。现在，假设您将此应用于 MSD 基数排序。由于每个新创建的堆栈帧都在要排序的两个范围中较小的一个上工作，因此您可以保证每个新堆栈帧中的元素数量是前一个堆栈帧的一半。因此，不是O(log U)。为了让你的堆栈爆炸，你需要一个真正天文数字的大输入数组，不管堆栈大小。

总结：你是对的，算法没有到位。但是，由于堆栈深度在简单实现中为 O(log U)，而在优化实现中为 O(log n)，因此除非您有一个简单的实现并且确实非常巨大，否则您不必担心这一点输入。

于 2015-08-26T20:02:46.943 回答
0

这个算法是就地的，因为它交换了来自数组两端的两个值。一个例子是：

{110,010,111,000,011}

0 bin 放在左边，而 1 bin 放在右边。从 MSD 开始，逐步排序如下：

{|110,010,111,000,010|}
{011|010,111,000|110}
{011,010|111,000|110}
{011,010,000||111,110}

在这个简化为 O(n) 的示例中，这可以在 O(3n) 时间内完成。唯一需要的额外内存是足够大的交换空间以容纳一个元素。

于 2014-03-02T13:53:53.060 回答