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

Question

我真的很困惑the "in-place" MSD radix sort算法:

Each bin is then processed recursively using the next digit, until all digits have been used for sorting.

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

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

那么，如何才能就地完成 MSD 基数排序？

Answer 1

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

你是正确的，MSD基数排序的空间使用与最大输入数字中的位数成正比。为符号简单起见，令 n 为输入数组的长度，U 为数组中的最大数。 MSD 基数排序的运行时间是 O(n log U)，因为数字 U 中的位数是 O(log U)。 O(log U) 是一个增长非常非常缓慢的函数。作为引用，宇宙中的原子数约为 10⁸⁰，即约 2²⁴⁰。因此，如果您要对由任何物理过程生成的数字进行排序，递归深度最多为 240，虽然很大，但绝对是可以管理的。

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

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