algorithm - MSD 与 LSD 基数排序

Question

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

MSD的优势：

1. 它可以处理可变长度的字符串
2. 它并不总是需要扫描整个字符串（它可以更快地决定顺序）
3. 可以使用插入排序来规避计数排序的缺点。

Answer 1

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

希望这可以帮助！

Answer 2

LSD 基数排序对我来说最大的优势是速度，因为它是无分支算法。对于相对较短的固定长度键，它使 LSD 基数排序成为可能的最快排序算法。LSD 的稳定性也是一个不错的特性。

Answer 3

@templatetypedef 总结得很漂亮。
MSD 基数排序可用于按字典顺序对键进行排序。
查看维基百科以获取工作示例和更清晰的信息。