algorithm - 线性排序下如何考虑桶排序？

Question

我想探讨一下我对桶排序的分析如下。
桶排序有多种实现方式。其中一些如下。
类型 1:
如果我们知道要排序的元素的范围，我们可以设置为每个可能的元素创建桶，然后将元素扔到它们对应的桶中。然后我们按顺序清空桶，结果是一个排序列表。在实现这个算法时，我们可以轻松地使用一个数组来表示我们的桶，其中值在每个数组索引将代表相应存储桶中元素的数量。如果我们有整数在范围 [0..max] 上，然后我们设置一个包含 (max + 1) 个整数的数组，并将所有值初始化为零。然后我们按顺序处理未排序的数组，读取每个元素的值，继续到桶数组中的相应索引，并增加那里的值。

时间:O(N)
空间:O(1)
类型 2:

示例:按年龄对一组人进行排序
年龄与用于排序的任意整数有些不同。因为它的范围很小 [0-150](所有人的年龄都在 0 到 150 之间)。所以最快的排序方法是分配151个链表(我们称它们为桶)并根据他/她的年龄将每个人的数据结构放入桶中:

时间:O(N+K)
空间:O(N+K)

类型 3(type2 的变体，如 Wikepedia 所示)

函数 nextSort 是一个排序函数，用于对每个桶进行排序。如果使用的插入排序比最差的将是 O(n^2) 或将使用合并排序，以便我可以保持比 O(nlgn) 的稳定性。

• 问题:
  1>怎么算线性排序，是因为Type 1还是Type 2？
  2>如果我像 WIkepedia 那样使用 Type 3，哪种排序对每个桶的排序效率更高？
  我知道在实践中使用插入排序的原因是我们希望桶很小，而对于小列表，插入排序比其他任何方法都快得多。即使在实现归并排序或快速排序时，当列表足够小时(比如低于 20 项左右)，也会使用插入排序。
  3>对于类型 3，我可以根据什么决定桶的范围？
  这很重要，因为如果您尝试使用大量桶(例如比 n 大得多)进行桶排序，则运行时间可能主要由扫描所有桶以查找您实际使用的桶所需的时间决定，即使其中大部分是空的。

我的分析基于:
Wikepedia
How could the complexity of bucket sort is O(n+k)?
Design and Analysis of AlgorithmsLecture notes for January 23, 1996
http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-23.html
How is the complexity of bucket sort is O(n+k) if we implement buckets using linked lists?
What is the worst case complexity for bucket sort?

Answer 1

类型 1:
您描述的第一种类型并不是真正的桶排序。它实际上是计数排序或关键索引计数。尽管它被认为是桶排序的变体。原因是因为您实际上只是在计算每个键的出现次数，而不是将键本身存储在存储桶中。

引用:http://en.wikipedia.org/wiki/Counting_sort
引用:http://www.cs.princeton.edu/courses/archive/spr13/cos226/demo/51DemoKeyIndexedCounting.pdf

Space: O(1)
we can set up buckets for each possible element,

这不是自相矛盾吗？您要为每个可能的元素声明桶并仍然保持 O(1)？ ;)

如果你希望算法稳定，你也不能覆盖输入数组。所以在实践中你需要 n + k 的空间要求:

• 长度为“n”的输出数组(基本上与输入数组大小相同)
• 'k' 个桶

如果您检查计数排序的伪代码，您会注意到最后一个循环再次遍历输入数组以查看每个元素需要到达的位置。通过按照它们在输入数组中出现的顺序执行此操作，您可以获得稳定的排序。

PS:请记住，您不一定要对整数进行排序。如果输入是 A-Z 之间的字符数组，您也可以使用此算法。

类型 2:

So the quickest way to sort it would be to allocate 151 linked lists (let's call them buckets)and put each person's data structure in the bucket according to his/her age:

这可能是最简单的方法，因为您可以很容易地找到所需的存储桶，但这不一定是最快的方法。例如，另一种可能性是每 10 年创建一次存储桶。

00 - 09
10 - 19
20 - 29
...

当你想往桶里插入东西时，你可以这样做:

• 对桶(例如 LinkedList)进行二分搜索以找到正确的位置
• 插入元素

这样您也不需要事后对桶进行排序，因为所有内容都已排序。并不是说这是一个好主意，只是指出了这种可能性。

问题:

1. 简单地说；它是线性排序，因为排序需要线性时间。类型 1 和类型 2 都采用 O(n + k)。另一个需要考虑的重要因素是桶排序使用的子算法来对每个单独的桶进行排序。如果使用快速排序，与例如冒泡排序相比，它将导致另一个下界。也可以选择具有不同边界的非比较子算法。一个很好的子算法选择和桶上的分布使得 bucketsort 不限于 O(n(log n)) 下限。请记住，O 表示法不提供任何速度保证，它提供增长率保证。如果您的输入大小从“N”加倍到“2N”，您的线性时间算法将比例如冒泡排序这样的 O(n^2)(最坏情况)算法更好地处理它。

2. 插入排序对于小型数组确实很有效，这也是选择它的主要原因。再加上它很稳定。因为如果不使用稳定的算法对桶本身进行排序，则整个算法(桶排序)将不稳定。

3. 很难说。我认为这取决于数据。如果您必须对 100 万个 32 位整数进行排序，则不会为它们创建 2^32 个桶。在这种情况下，最好看看其他算法(例如 LSD Radix 排序)，它基本上会创建 9 个桶(每个数字 1 个)。