Meh*_*dad 5 stack-overflow sorting algorithm in-place radix-sort
我真的很困惑“就地”MSD基数排序算法：
然后使用下一个数字递归处理每个 bin，直到所有数字都用于排序。
我很困惑，因为在我看来递归意味着 O(n) 堆栈空间，其中n是最长字符串的长度（位数），对吗？
在我看来，避免堆栈溢出的唯一方法是使用堆空间——但是根据任何定义，算法不再是“就地”。
那么，如何就地完成就地 MSD 基数排序呢？
我认为术语“就地 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)，因此您不需要担心这一点，除非您有一个简单实现并且确实非常巨大输入。