我想在下面探讨我对桶排序的分析。
桶排序有很多种实现方式。其中一些如下:
1型:
如果我们知道要排序的元素的范围，我们就可以建立将每个可能的元素放入桶中，然后将元素放入相应的桶中。然后,我们按顺序清空桶，结果是一个排序列表。在实现这个算法时，我们可以很容易地使用一个数组来表示桶，其中的值为每个数组索引将表示相应桶中的元素数量。如果我们有整数在[0..]Max]，然后我们建立一个(Max + 1)整数数组，并将所有值初始化为零。然后按顺序遍历未排序数组，读取每个元素的值，然后
时间:0 (N)
空间:O (1)
2型:
示例:按年龄对一组人进行排序
年龄与用于排序的任意整数有些不同。因为它的范围很小[0-150](所有人的年龄都在0-150岁之间)。因此，排序的最快方法是分配151个链表(我们称之为桶)，并根据每个人的年龄将每个人的数据结构放入桶中:
时间:0 (N+K)
空间:O (N + K)
Type 3(维基百科中Type 2的变体)
函数nextSort是对每个桶进行排序的排序函数。如果使用插入排序，那么最坏的情况将是O(n^2)，或者使用归并排序，这样我可以保持比O(nlgn)更稳定。
-
问题:
它是如何被认为是线性排序的，是因为类型1还是类型2?
2>如果我像维基百科一样使用类型3，哪种排序对每个桶有效?
我知道在实践中使用插入排序的原因是我们希望桶很小，对于小列表，插入排序比其他任何方法都快得多。即使在实现归并排序或快速排序时，当列表足够小时(例如低于20个项目)也会使用插入排序。
3>对于类型3，我可以在什么基础上决定桶的范围?
这很重要，因为如果您尝试对大量的桶进行桶排序，例如远远大于n，则运行时可能会被扫描所有桶寻找您实际使用的桶所需的时间所支配，即使大多数桶是空的。
我做的分析基于:
Wikepedia
桶排序的复杂度怎么会是O(n+k)呢?
算法的设计与分析1996年1月23日的课堂讲稿
http://www1bpt.bridgeport.edu/狄克特/莉莉bucketsort.htm
http://cs.nyu.edu/courses/fall02/v22.0310 002/lectures/lecture - 23. - html
如果我们使用链表实现桶排序，那么桶排序的复杂度如何为O(n+k) ?
桶排序的最坏情况复杂度是多少?
类型1:
你描述的第一种类型并不是真正的桶排序。它实际上是计数排序或键索引计数。尽管它被认为是桶排序的一种变体。原因是您实际上只是计算每个键的出现次数，而不是将键本身存储在bucket中。
Ref: http://en.wikipedia.org/wiki/Counting_sort
裁判:http://www.cs.princeton.edu/courses/archive/spr13/cos226/demo/51DemoKeyIndexedCounting.pdf
空间:O (1)
我们可以为每个可能的元素设置bucket
这不是矛盾吗?你打算为每一个可能的元素都声明一个桶并且仍然保持0 (1)?;)
如果希望算法稳定，也不能覆盖输入数组。所以在实际操作中，
需要n + k的空间需求- 长度为'n'的输出数组(基本上与输入数组大小相同)
- "k"桶
如果检查计数排序的伪代码，您将注意到最后一个循环再次遍历输入数组，以查看每个元素需要放到哪里。通过按照它们在输入数组中出现的顺序执行此操作，您将获得一个稳定的排序。
PS:请记住，您不一定要排序整数。如果输入是A-Z之间的字符数组，也可以使用此算法。
2型:所以最快的排序方法是分配151个链表(让我们称之为桶)并根据年龄将每个人的数据结构放入桶中:
这可能是最简单的方法，因为您可以很容易地找到所需的bucket，但它不一定是最快的方法。例如，另一种可能性是每10年创建一个桶。
00 - 09
10 - 19
20 - 29
…
当你想要插入一些东西到bucket中时，你可以这样做:
- 对桶(例如LinkedList)进行二进制搜索以找到正确的位置
- 插入元素
这样，您也不需要在之后对桶进行排序，因为所有内容都已经排序了。不是说这是个好主意，只是指出了这种可能性。
问题:
简单地说;这是线性排序，因为排序需要线性时间。类型1和类型2都需要O(n + k)。另一个需要考虑的重要因素是桶排序用于对每个单独的桶进行排序的子算法。如果使用快速排序，则会导致与冒泡排序(例如冒泡排序)相比的另一个下限。也可以选择具有不同边界的非比较子算法。子算法的一个好的选择和桶的分布使得桶排序不局限于O(n(log n))的下界。记住，0符号并不能保证速度，它只能保证增长率。如果你的输入大小从'N'翻倍到'2N'，你的线性时间算法将比像bubblesort这样的O(N ^2)(最坏情况)算法更好地处理它。
插入排序对于小数组确实是有效的，这是选择它的主要原因。加上它是稳定的。因为如果你不使用一个稳定的算法来对桶本身排序，那么整个算法(桶排序)就不会是稳定的。
不好说。在我看来，这取决于数据。如果你要排序一百万个32位整数，你不会为它们创建2^32个桶。在这种情况下，最好看看其他算法(例如LSD基数排序)，它基本上会创建9个桶(每个数字1个)。
桶排序是线性时间，即每个桶按线性时间排序。"类型1"one_answers"类型2"都是线性时间的，因为每个桶中的所有值两两比较相等，不需要进一步排序。
后两个问题的答案在实践中是有效的。通常，标准库排序的编写者已经确定了插入排序的适当截止。我认为桶排序的性能在很大程度上取决于所讨论的数据和内存子系统。
您描述的类型1和类型2实际上是相同的意思，您有一个范围。是的，在这种情况下，它是线性时间复杂度，因为在每个桶中不需要进一步排序。每个存储桶包含一种类型的值。