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

Question

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

谢谢

Answer 1

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

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

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

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

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

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

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

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