"In-place" MSD基数排序、堆栈空间和Stack Overflow的问题

Question

我对“原地” MSD 基数排序算法感到非常困惑：链接 每个箱子都使用下一个数字进行递归处理，直到所有数字都用于排序。

我感到困惑，因为递归似乎意味着O(n)堆栈空间，其中n是最长字符串（以位数计）的长度，对吗？

在我看来，避免堆栈溢出的唯一方法是使用堆空间--但是这时算法不再是任何定义下的“原地”。

那么，如何才能实现“原地”的MSD基数排序呢？

- user541686

---

考虑在cs.stackexchange.com上提出与计算机科学相关的问题。 - Realz Slaw

@RealzSlaw：我完全忘记了那个网站，谢谢。 - user541686

Answer 1

我认为术语“原地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 n）-而不是O（log U）。为了使其爆炸，您需要一个真正巨大的输入数组，无论堆栈大小如何。

总之：您是正确的，该算法不是原地的。但是，由于在朴素实现中堆栈深度为O（log U），在优化实现中为O（log n），因此除非您有朴素实现并且输入真正巨大，否则不必担心这个问题。

- templatetypedef

---

+1 感谢。请注意，这不仅仅适用于数字；字符串可以任意长。 （之所以提到这一点，是因为您提到了宇宙中的原子数量。） - user541686

Answer 2

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

{110,010,111,000,011}

0 二进制位放在左边，而 1 二进制位则放在右边。从最高有效位开始，逐步排序如下：

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

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

- Norbles