MSD与LSD基排序

Question

我不知道为什么有人会用LSD基排序。

MSD的优势：

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

Answer 1

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

希望这能有所帮助！

Answer 2

@templatety胡枝子把它总结得很好。

MSD基排序对于在词典顺序中对键进行排序非常有用。

看看维基百科的工作示例和更清晰的信息。

Answer 3

对我来说，LSD基排序的最大优点是速度快，因为它是无分支算法。它使LSD基排序速度最快，对相对较短的固定长度键进行排序。LSD的稳定性也很好。