我已阅读有关此主题的多个来源。但是，我无法弄清楚这些公式的确切含义。当 b = n 时，基数排序似乎是线性的。这是否意味着我应该将基数设置为数组的长度？
如果我有一个包含 1 亿个整数的数组，范围是 0 到 10 亿，我应该选择以 1 亿为底数吗？
如果这不正确，请尝试为我简化它。我能找到的大多数基数排序示例仅以 10 为基数或以 2 为基数，因此它们对于分别大于 10 或 2 的数组来说速度很慢，或者我就是不明白。
感谢您的帮助。
最佳答案
当您将基数设置为数组中的条目数时，基数排序实际上并不是线性时间。基数排序的运行时间为 O(n logb U)，其中 n 是数组中元素的总数，b 是选择的基数，U 是数组中的最大元素数。如果设置 b = n，则运行时间为 O(n logn U) = O(n log U/log n)。渐近地，这真的很棒!
但在实践中，其他因素在评估基数排序时往往更为重要。一方面是将数字拆分为单个数字的成本。使用一个 2 的幂的基数，这只是一个简单的移位。对于其他基地，您可能需要使用(相对)更昂贵的部门，这可能会造成一些伤害。不过，更重要的是，有引用地点。如果您使用基数 b，那么您将拥有 b 个不同的数组，元素将被放入其中。如果您选择的 b 太高，那么在将元素附加到桶数组的末尾时，缓存性能可能会很差，这实际上会导致性能下降。
可能最好的想法是根据不同的基本选择实际分析程序，看看什么是最好的。根据经验，当我尝试使用 base-n 基数排序时，我发现它在大输入上比标准的 base-2 基数排序慢，这主要是由于局部性问题。我猜想 2 不是基数排序的理想基础，但是像 216 这样大的东西可能会开始遭受缓存未命中的困扰。尝试试验并让我们知道您的发现!
希望这对您有所帮助!
关于performance - 基数排序的最佳基础，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23145573/