algorithm - 什么时候使用基数排序合适？

Question

您能够使用基数排序对您的数据有哪些限制？

如果我正在对大量整数进行排序，是否适合使用基数排序？为什么基数排序没有更多使用？

Answer 1

当您拥有大量数据且键受到某种限制时，这非常棒。例如，当您需要对一个 100 万个 64 位数字的数组进行排序时，可以使用它按 8 个最低有效位排序，然后按接下来的 8 个，依此类推（应用 8 次）。这样，这个数组可以按 8*1M 操作排序，而不是 1M*log(1M)。

Answer 2

桶排序在离散键值的数量相对于数据项的数量较小的情况下很有用，并且目标是在不干扰原始列表的情况下生成列表的重新排序副本（因此需要维护旧的和新版本的列表同步不是负担）。如果可能的键数量太大而无法在单次遍历中处理，则可以通过多次遍历将桶排序扩展为基数排序，但会失去桶排序为小键提供的大部分速度优势。

在一些外部排序场景下，尤其是当不同键值的数量非常少（例如两个）时，需要一个稳定的排序，而 I/O 设备只能对一个顺序数据流进行高效操作，可能有用make K 通过源数据流，其中 K 是键值的数量。在第一次通过时，复制键是最小合法值的所有项目并跳过其余部分，然后复制键是下一个更高值的所有项目，跳过其余部分，等等。这种方法显然非常有效如果有很多不同的键值，但如果有两个就很好了。

Answer 3

如果您知道整数值的范围，并且它不是太大，那么在您的情况下，计数排序
可能是一个更好的选择。

Answer 4

您可能不会像您想象的那样经常看到它的一个原因是基数排序不像基于比较的排序（快速排序/合并排序/堆排序）那样通用。它要求您可以将要排序的项目表示为整数或类似整数。使用标准库时，很容易定义一个比较任意对象的比较函数。定义将任意数据类型正确映射为整数的编码可能更难。