MSD vs LSD基数排序

我不确定为什么有人会使用LSD基数排序。 MSD的MSD vs LSD基数排序

优点：

它可以处理可变长度的字符串
它并不总是需要扫描整个字符串（它CA决定有关订单越快）
人们可以使用插入排序来规避计数排序的缺点。

2014-01-12 user1377000

考虑以数字顺序排序整数，而不是按字典顺序排序字符串。有关更详细的回复，您应该尝试http://cstheory.stackexchange.com/ – beaker

@ beaker- cstheory.stackexchange.com是针对研究级别的CS问题的。我认为这不合适。 – templatetypedef

@templatetypedef糟糕的剪切和粘贴作业，对不起。我正在寻找http://cs.stackexchange.com/，由于某种原因，它不会出现在页面底部的便利列表中。 – beaker

LSD基数排序优于MSD基数排序的一个优点是LSD基数排序是一个稳定的排序 - 如果有多个元素用相同的键排序，它们将以相同的相对顺序结束当您运行LSD基数排序时排序的输出，但如果您运行MSD基数排序可能不会排序。如果您要对键/值对进行排序，并且要保留原始相对排序，则LSD基数排序将优于MSD基数排序。

希望这会有所帮助！

来源

2014-01-12 17:29:06 templatetypedef

为什么MSD radix不是一个稳定的排序算法？即使在这里，我们使用计数排序（这是稳定的）来排序数字，但从MSB权利？ – Zephyr

@Zephyr MSD基数排序的某些实现 - 特别是二进制MSD基数排序 - 使用像quicksort那样的不稳定的分区策略。你可以稳定地做，但不是必需的。查看“二进制快速排序”以了解更多信息。 – templatetypedef

是的，如果我们使用快速排序，那么它会不稳定。但是你能告诉我为什么我们不能使用计数排序来对存储桶内MSB相同的元素进行排序？ – Zephyr

@templatetypedef对它进行了精美的总结。
MSD基数排序可用于对lexicographic order中的键进行排序。
查看wikipedia的工作示例和更清晰的信息。

来源

2014-01-12 19:13:45

非常感谢。那么，整数的字典顺序是自然顺序。我不认为这两种基数排序变体试图达到什么不同。 – user1377000

@ user1377000是的，基本上两者都在整数和字符串上执行类似，从相同方向开始提供。一般来说，词典顺序是从左到右实现的，并且按从右到左的顺序排列。 –

对我来说LSD基数排序的最大优点是速度，因为它是无分支算法。它使得LSD基数排序算法对于较短的固定长度密钥可能是最快的排序算法。 LSD的稳定性也很好。

来源

2014-01-12 20:49:10

MSD vs LSD基数排序

回答

相关问题