基数排序:LSD与MSD版本

Question

"算法简介"一书提到了基数排序的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 对于小文件来说太慢了，它需要对小文件进行大量的递归调用。