为什么使用已排序的输入时桶排序运行得更快？
我正在用Java实现bucket排序，我发现当输入数组被排序（升序或降序）时，它的排序（升序）比随机排序快。为什么会这样？据我所知，它只是遍历数组，并在每个元素的索引处递增“tally”数组。我不明白为什么排序后的输入会运行得更快，但速度似乎是原来的两倍。
谢谢
共有1个答案
原因很可能是由于空间局部性和排序输入集的较高缓存命中率。
如果您对输入进行了排序，则同一邻域中的bucket相对会获得一系列命中率，并且随着您的排序输入移动到更高的范围，下一个bucket邻域将开始获得命中率。
考虑一个简化的例子来说明这一点：
假设您有10个桶，每个桶的范围大小为1000：
[0-999], [1000-1999], ..., [9000-9999]
假设您一次只能缓存对一个桶的引用（这是人为的部分，但实际上想法是一样的：
现在假设您的输入集是介于[0-9999]
- 如果对输入进行排序，每个存储桶将恰好获得一个初始缓存未命中，然后是多个缓存命中，直到输入中的序列进入下一个存储桶的范围
- 如果您有未排序的输入，在最坏的情况下，缓存将始终丢失，并将另一个bucket加载到缓存中，并且只会再次丢失，因为未排序序列中的下一个数字将查找另一个bucket
-
所以我偶然发现了基于非比较排序的算法桶排序，确切地说，我不知道为什么它是好的。 我有一个想法，但我需要有人来证实。 假设我想对1000个元素数组进行排序。如果它被均匀地分配并扣入10个桶中，每个桶有100个元素。 使用n log（n）算法对100个元素进行10次排序=10*100 log（100）=1000 log（100）=2000 使用n log（n）算法对1000个元素进行排序时=1000
-
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入
-
我已经在链接中看到了(http://bigocheatsheet.com/)插入排序的复杂性与冒泡排序相同，堆排序也优于这两种排序。但是，当我创建一个示例程序并比较插入排序所花费的时间时，我感到难以置信。 类用于测试排序算法。 泡泡排序类 用于插入排序的类 堆排序类 用于创建数组的类 我尝试了所有的情况，比如最好的情况、最坏的情况和一般情况。但在所有情况下，插入排序都比冒泡排序和堆排序快得多。理论
-
我正在学习Python和一些基本的数据结构和算法。我实现了自己版本的合并排序，但我不明白为什么它会改变输入数组的顺序。它的行为就像我在mergesort（）函数中将输入数组作为全局引用一样，但我没有这样做。从我实现代码的方式来看，我认为应该在函数的本地范围内对输入数组的副本进行排序，然后返回该副本的排序版本，保持输入数组不变。然而，事实并非如此。它正确地对数组排序；我只是被一个似乎是范围问题的问题
-
主要内容：桶排序算法的实现思路,桶排序算法的具体实现桶排序（又称箱排序）是一种基于分治思想、效率很高的排序算法，理想情况下对应的时间复杂度为 O(n)。 接下来，我们系统地学习一下桶排序算法。 桶排序算法的实现思路 假设一种场景，对 {5, 2, 1, 4, 3} 进行升序排序，桶排序算法的实现思路是： 准备 5 个桶，从 1~5 对它们进行编号； 将待排序序列的各个元素放置到相同编号的桶中； 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一
-
问题：Mergesort将一个数字列表分成两半，并对这两个数字进行递归调用。相反，您能在左半部分执行quicksort，在右半部分执行mergesort吗？如果是，则通过显示每个步骤来显示它将如何对下面的数字列表进行排序。如果没有，请解释为什么不能。 Iam应该使用MergeSort对数字列表进行排序。左半部分将使用快速排序进行排序？ 我想出来了。安：是的，我们可以 使用mergeSort对数组的