放置“MSD基数排序，堆栈空间和堆栈溢出
我真的很困惑“就地”的MSD基数排序算法：
然后使用下一个数字递归处理每个仓，直到所有数字已用于排序。
我很困惑，因为在我看来，递归意味着O（n）堆栈空间，其中n是最长字符串的长度（以位数为单位），对吗？
在我看来，避免堆栈溢出的唯一方法是使用堆空间 - 但随后算法不再由任何定义“就地”了。
那么，怎样才能在原地进行MSD基数排序呢？
我认为术语“就地MSD基数排序”有点让人误解，因为正如你所指出的那样，它不是一种在“原地”严格定义下的就地算法。 这里的“就地”术语很可能指的是，与LSD基数排序不同，该算法不需要辅助数组来临时存储来自原始输入数组的元素。
MSD基数排序的空间使用量与最大输入数字中的位数成正比，这是正确的。 为了符号简单，让我们有n是输入数组的长度，U是数组中最大的数字。 MSD基数排序的运行时间是O（n日志U），因为数字U中的位数是O（log U）。 O（log U）是一个非常缓慢增长的函数。 作为参考，宇宙中的原子数是大约1080，大约是2240.因此，如果你排序的是由任何物理过程产生的数字，递归深度将最多为240，而大的绝对可管理。
如果你排序的数量真的很大 - 比如说数字和数千位的数字 - 那么你就有必要担心吹出堆栈。 然而，我认为如果你有很好的MSD基数排序实现，这种情况极不可能发生。 在quicksort中有一个标准优化 - 看起来很像MSD radix排序 - 在两个分段递归调用中，您不必进行递归调用，而是在两个范围中较小的一个范围内进行排序，然后将堆栈框架从初始调用回收到整理更大的范围。 （这实质上是一个尾巴消除）。 现在，假设您将此应用于MSD基数排序。 由于每个新创建的堆栈帧都可以在两个范围中较小的一个范围内进行排序，因此可以保证每个新堆栈帧的元素都比前一个堆栈帧少一半。 结果，堆栈可以达到的最大深度是O（log n） - 而不是O（log U）。 为了让你的堆栈发泄，你需要一个真正的天文大型输入数组，无论堆栈大小如何。
总之：你说得对，算法不适用。 但是，由于在初始实现中堆栈深度为O（log U）并且在优化实现中O（log n），所以除非您有一个天真的实现并且确实极其庞大，否则不需要担心这一点投入。
这个算法是就地的，因为它交换了来自阵列两端的两个值。 一个例子是：
{110,010,111,000,011}
0箱位于左侧，1箱位于右侧。 从MSD开始，一步一步地排序如下：
{|110,010,111,000,010|}
{011|010,111,000|110}
{011,010|111,000|110}
{011,010,000||111,110}
这可以在O（3n）时间完成，在这个例子中简化为O（n）。 所需的唯一额外内存是交换空间足够大的一个元素。
链接地址: http://www.djcxy.com/p/70801.html上一篇: place" MSD radix sort, stack space, and Stack Overflow's