基数排序：LSD与MSD版本

Question

"算法导论"一书提到了基数排序的LSD（最低有效位）版本。然而，在stackoverflow上，其他人已经指出了MSD（最高有效位）版本的存在。因此，我想了解每个版本的优缺点。我猜LSD版本比MSD版本有一些优势，但我不确定。因此提出这个问题。

- Geek

---

这是一个无效的问题，因为两种变体都存在，但具有略微不同的属性。 - unkulunkulu

好的，但这并不改变问题。您应该沿着“MSD和LSD之间的区别，优缺点等方面”进行提问。 - unkulunkulu

好的，现在我相信这是一个好问题。 - unkulunkulu

优缺点可能高度依赖于您的问题域和预期使用。例如，对于在1000到3000之间的整数列表进行基数排序，使用LSD版本可能更好，因为LSD具有更大的可能值集，允许将问题分解为更多平均较小的子问题，而不是MSD方法。 - twalberg

@twalberg，据我所知，基数排序的每一次操作都是O(n)，因此每个子问题的大小并不重要。您能详细解释一下吗？ - Mark Ransom

如果每次遍历都是真正的O(n)，那么从时间复杂度的角度来看，你是正确的。然而，根据我回忆起来的情况，自从我写下那条评论以来已经过去了3.5年，我当时设想了会产生分页/交换性能开销的大型数据集，这种情况下最好将问题分成10个O(N/10)子问题，从而可能消除不适合主内存的额外成本，而不是2个O(N/2)子问题，这些子问题可能仍然存在容量问题。类似的评论也适用于较小子问题的L1/L2/L3缓存性能... - twalberg

Answer 1

从链接中获取的内容可能会很有用：http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx（在页面底部）

LSD基数排序的最大问题是从使差异最小的数字开始。如果我们能够从最重要的数字开始，第一次排序就可以完成整个范围的排序，之后的每次排序只需要处理细节。 MSD基数排序的想法是将具有相同值的所有数字分成自己的桶中，然后对所有桶执行相同的操作，直到数组排序。自然地，这建议使用递归算法，但这也意味着我们现在可以对可变长度的项目进行排序，并且我们不必触摸所有数字即可获得排序的数组。 这使MSD基数排序更快，更实用。

- Roman Dzhabarov

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。

- user2558887

---

快速排序使用lg(n)额外的空间用于递归栈（或等效）。MSD基数排序可以只使用递归栈（或等效）额外的空间，因为它不需要稳定性来保证正确性，所以它可以比LSD基数排序使用更少的空间。 - ReneSac

Answer 3

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

- M.J.Watson