24

“算法简介”一书提到了基数排序的 LSD（最低有效位）版本。但是，正如其他人在 stackoverflow 中指出的那样，还存在 MSD（最高有效位）版本。所以我想知道这些的优缺点。我的猜测是 LSD 版本比 MSD 版本有一些好处，但我不确定。因此问题。

4

3 回答 3

11

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

LSD 基数排序的最大问题是它从差异最小的数字开始。如果我们可以从最重要的数字开始，那么第一遍将大大有助于对整个范围进行排序，之后的每一遍都会简单地处理细节。MSD基数排序的思想是将所有具有相等值的数字划分到自己的桶中，然后对所有桶做同样的事情，直到数组被排序。自然地，这暗示了一种递归算法，但这也意味着我们现在可以对可变长度的项目进行排序，并且我们不必接触所有数字来获得排序后的数组。这使得 MSD 基数排序更快更有用。

于 2012-08-14T00:07:34.587 回答
7

正如在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。

于 2016-01-03T02:41:31.707 回答
5

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

于 2016-02-27T14:40:19.653 回答