桶排序与快速排序
桶排序与快速排序
提问于 2014-10-31 02:18:12
一般问题:为什么桶排序比快速排序更有益？
假设数字来自流，而我的桶类似于(1,10) (11,20)等等。
然后我分类桶，然后把它们放在一起，得到我的排序数字。
或
我可以把它们放在一个数组中，然后用快速排序对它们进行排序。
- 桶类分类: Bestcase O(N + K)最差(N^2)；
- 快速排序: Bestcase O(1) Averagecase O(nlogn)最坏(N^2)；
那么，为什么我们要对想要排序的传入整数流使用桶排序呢？是因为我们可以根据每个桶中整数的数量来做出决定吗？
谢谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-10-31 02:30:09
如果我们预先知道k，并且它很小(k << n)，则桶排序可以比快速排序更有效地运行，因为n*log (n )，快速排序的平均值将超过(n+ k)，这是桶排序的平均值。
也就是说，
sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list);它可能被用于流的一个原因，是桶排序已经到位。您可以维护排序列表，有效地添加新元素，而不必每次都对其重新排序。您只需直接操作数据结构(桶)，就这样。
另一方面，快速排序不到位，需要完整的排序运行才能返回排序列表。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26666571
复制相关文章
相似问题
腾讯云开发者
