java - 桶排序与快速排序

Question

一般问题:为什么桶排序比快速排序更有利？

假设数字是从流传入的，我的存储桶就像 (1,10) (11,20) 等。

然后我对桶进行排序，然后将它们放在一起，得到排序后的数字。

或者

我可以将它们放入一个数组中，然后使用快速排序对它们进行排序

• 桶排序:最好情况 O(N + K) 最坏情况 (N^2)；
• 快速排序:最佳情况 O(1) 平均情况 O(nlogn) 最坏情况 (N^2)；

那么为什么我们要使用桶排序来处理我们想要排序的传入整数流之类的事情呢？是因为我们可以根据你每个桶中的整数个数来做出决定吗？

谢谢

Answer 1

如果我们预先知道 k，并且它很小 (k << n)，那么桶排序可以比快速排序高效地运行得更快，因为快速排序的平均值 n*log(n) 将大于 (n + k)，这是桶排序的平均值。

即，

sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list);

它可用于流的一个原因是桶排序是就地的。您可以维护排序列表，有效地添加新元素，而不必每次都重新排序。您只需直接操作数据结构(桶)即可。

另一方面，快速排序不是就地排序，需要完整的排序运行才能返回排序后的列表。