radix排序的实际应用

Question

当您知道密钥在某个有限范围内，例如$ n $值在$ [0 dots n^k -1] $中，例如，Radix排序在理论上非常快。如果$ k < lg n $，您只需将值转换为基本$ n $，该$ n $需要$ theta（n）$ time，进行基本$ n $ radix排序theta（nk）$算法。

但是，我读过 实际上，radix排序通常比这样做的速度要慢得多:

对于大型阵列，Radix排序的指令数量最低，但是由于其缓存性能相对较差，因此其总体性能比Mergesort和QuickSort的内存优化版本要差。

Radix排序只是一种不错的理论算法，还是具有常见的实际用途？

Answer 1

在实践中，Radix通常是平行机上最快，最有用的类型。

• Zagha和Blelloch：用于矢量多处理器的radix排序。 超级计算, 1991: 712-721.
• BLELOCH，LEESERSON，MAGGS，PLAXTON，SMITH和ZAGHA：连接机CM-2的分类算法的比较。 Symp平行算法和ARCH （SPAA-3）：3-16，1991。
• Arpaci-Dusseau，Arpaci-Dusseau，Culler，Hellerstein和Patterson：在工作站网络上进行高性能分类。 conf关于数据的MGT, ，（Sigmod-1997）：243-254。
• Arpaci-Dusseau，Arpaci-Dusseau，Culler，Hellerstein和Patterson。搜索排序记录：现在调整的体验。 ACM Sigmetrics Symp平行和分布式工具, ，（SPDT-2）：124-133，1998。

在多处理器的每个节点上，您可能会执行类似QuickSort的操作，但是Radix排序允许多个节点以比各种递归类型的同步少。

还有其他情况。如果您需要一个 稳定排序 （每当两个键相等时，它们都以相同的顺序而不是重新排列）。 Mergesort也是稳定的（如果正确实现）。您的链接是我第一次听说有人说Mergesort可以比Radix排序具有更好的缓存行为。

Answer 2

@Robert：您的链接非常令人惊讶（实际上我找不到引用的句子）。我的个人经验是随机输入，radix排序比STL快得多 std::sort(), ，使用QuickSort的变体。我曾经通过更换算法快50％的算法 std::sort() 带有不稳定的radix排序。我不确定QuickSort的“内存优化版本”是什么，但我怀疑它的速度可能是STL版本的两倍。

这篇博客文章 评估了radix排序以及其他几种排序算法。简而言之，在此评估中， std::sort() 花费5.1秒才能排序5000万个整数，而原位/不稳定的Radix排序需要2.0秒。稳定的radix排序应该更快。

radix排序也广泛用于稳定排序字符串。 Radix排序的变体有时是用于构造后缀阵列，BWT等的变体。

Answer 3

radix排序也是在固定字母上分类固定长度单词的自然方法，例如Kärkkäinen和Sanders算法（http://www.cs.cmu.edu/~guyb/realworld/papersss04/kasa03.pdf)