algorithm - 为什么桶排序在输入排序后运行得更快？

Question

我在 Java 中实现桶排序，我发现当输入数组排序(升序或降序)而不是随机排序时，它排序(升序)更快。为什么是这样？据我了解，它只是遍历数组并在每个元素的索引处递增“计数”数组。我不明白为什么使用排序的输入它会运行得更快，但它似乎快了两倍。

谢谢

Answer 1

原因很可能是由于空间局部性和排序输入集的缓存命中率更高。

如果您对输入进行了排序，则同一邻域中的桶相对会获得一堆命中，并且当您的排序输入移至更高范围时，下一个桶邻域将开始获得命中。

考虑一个简化的例子来说明这一点:

假设您有 10 个范围大小为 1,000 的桶:

[0-999], [1000-1999], ..., [9000-9999]

并且假设您一次只能缓存对一个桶的引用(这是人为的部分，但在实践中这个想法是相同的:

现在假设您的输入集是 [0 - 9999] 之间的随机数

• 如果输入已排序，每个桶将得到恰好一个初始缓存未命中，然后是多次缓存命中，直到输入中的序列移动到下一个桶的范围内。
• 如果您有未排序的输入，在最坏的情况下，缓存总是会丢失，将另一个桶加载到缓存中，只会再次丢失，因为未排序序列中的下一个数字将寻找另一个桶。