基数排序: LSD与MSD版本

Question

"Introduction to Algorithms"一书提到了基数排序的LSD (最低有效位)版本。然而，正如其他人在stackoverflow中指出的那样，MSD (最重要的数字)版本也存在。所以我想知道每种方法的优缺点。我的猜测是LSD版本比MSD版本有一些好处，但我不确定。这就是问题所在。

Answer 1

取自链接，可能有用：http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (在最底部)

LSD基数排序最大的问题是它从差异最小的数字开始。如果我们可以从最重要的数字开始，第一次传递将对整个范围进行很长一段时间的排序，之后的每一次传递都将简单地处理细节。MSD基数排序的思想是将所有具有相同值的数字划分到它们自己的存储桶中，然后对所有存储桶执行相同的操作，直到对数组进行排序。当然，这是一种递归算法，但这也意味着我们现在可以对可变长度的项进行排序，而不需要接触所有的数字来获得排序的数组。这使得MSD基数排序速度更快，更有用。

Answer 2

正如在Algorithms一书中所读到的，LSD和MSD都是字符串数组排序算法，基于所谓的键索引计数而不是比较。因此，LSD和MSD的运行时间与传统的快速排序或合并排序不同。

正如Dzhabarov提到的，LSD和MSD之间最大的区别是MSD首先考虑最重要的数字或字符，这本质上是对字符串进行排序，而不是迭代字符串中的所有数字。这是一个优势。然而，MSD的递归实现比LSD使用更多的空间。

下表说明了快速排序、LSD和MSD之间的部分区别。

algorithm    running time              extra space
quicksort    N(lgN)^2                  1
LSD          NW                        N
MSD          between N and NW          N + WR

其中N是数组的长度，W是字符串的长度，R是基数的大小。

PS:正如书中提到的，Java系统排序使用具有快速字符串比较的通用排序算法，而不是LSD或MSD。

Answer 3

当存在固定长度时，LSD比MSD更快。MSD对于小文件来说太慢了，而且它需要在小文件上进行大量的递归调用。