桶分类与快速排序

一般问题：为什么桶分类更有利于快速排序？桶分类与快速排序

可以说数字是从流中传入的，而我的存储区就像（1,10）（11,20）等。

然后我分拣桶，然后把它们放在一起，有我的排序数字。

我可以把它们放在一个数组，然后将它们与快速排序

桶排序排序：Bestcase O（N + K）最坏情况下（N^2）; （1）平均情况O（nlogn）最坏情况（N^2）;

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

感谢

来源

2014-10-31 k9b

Quicksort的最佳情况不是* O（1）*它是[* O（n）*]（http://en.wikipedia.org/wiki/Quicksort）。 – EJP 2014-10-31 02:33:05

我相信他在开玩笑。 – habitats 2014-10-31 02:34:58

@EJP是的，我在做一个关于http://www.dangermouse.net/esoteric/intelligentdesignsort.html的笑话。我在笑话方面真的很糟糕。我应该停止尝试制作它们。 – 2014-10-31 02:36:09

如果我们知道k上一前，它是小（K < < N）则桶排序可以高效地运行比快速排序更快，因为N *的log（n），平均为快速排序，将大于（n + k），这是桶排序的平均值。

即，

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

它可用于流A的理由，是就地该桶排序是。您可以维护排序列表，有效添加新元素，而无需每次重新排序。你只是直接操纵数据结构（桶），就是这样。

另一方面，Quicksort不在位，并且需要完整的排序才能返回排序列表。

来源

2014-10-31 02:30:09 habitats

谢谢！如果你不介意，还有两个后续问题。 1.所以..如果这是一个大流，或者我们没有被告知大小的流，那么使用Quicksort可能是有益的。 2.为什么有时候O（n + k），我已经阅读了一些解决方案，但它的deosnt对我来说意义重大，因为它应该是 – k9b 2014-10-31 02:32:31

请接受答案，如果它是令人满意的，btw – habitats 2014-10-31 02:40:16

Yea soz刚刚回来。感谢您的回答 – k9b 2014-10-31 03:01:23

桶分类与快速排序

回答

相关问题