5

我想探索我对桶排序的分析，如下所示。
桶排序有多种实现方式。其中一些如下。
类型 1：
如果我们知道要排序的元素的范围，我们可以为每个可能的元素设置桶，然后将元素扔到它们对应的桶中。然后我们按顺序清空桶，结果是一个排序列表。在实现这个算法时，我们可以很容易地使用一个数组来表示我们的桶，其中每个数组索引处的值将代表相应桶中元素的数量。如果我们有 [0..max] 范围内的整数，那么我们设置一个 (max + 1) 个整数数组并将所有值初始化为零。然后我们依次遍历未排序的数组，读取每个元素的值，转到 buckets 数组中的相应索引，并在那里增加值。

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

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

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

类型 3（类型 2 的变体，如维基百科所示）

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

  • 问题：
    1>如何认为是线性排序，是因为Type 1还是Type 2？
    2>如果我使用像 WIkepedia 这样的类型 3，哪种排序对每个桶进行有效排序？
    我知道在实践中使用插入排序的原因是我们希望桶很小，而对于小列表，插入排序比其他任何方法都快得多。即使在实现合并排序或快速排序时，当列表变得足够小时（比如低于 20 项左右）时，也会使用插入排序。
    3>对于类型 3，我可以在什么基础上决定存储桶的范围？
    这很重要，因为如果您尝试使用大量存储桶（例如远大于 n）进行存储桶排序，则运行时可能会受到扫描所有存储桶以查找您实际使用的存储桶所需的时间的支配，即使其中大部分是空的。

我做了分析基于：
维基百科
桶排序的复杂性怎么可能是O（n + k）？
算法设计与分析 1996 年 1 月 23 日讲义
http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
http://cs.nyu.edu/courses/fall02/V22.0310-002/ Lectures/lecture-23.html
如果我们使用链表实现桶，桶排序的复杂度是 O(n+k)？
桶排序的最坏情况复杂度是多少？

4

3 回答 3

5

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

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

空间：O(1)
我们可以为每个可能的元素设置桶，

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

如果您希望算法稳定，也不能覆盖输入数组。因此，在实践中，您需要 n + k 空间要求：

  • 长度为“n”的输出数组（基本上与输入数组的大小相同）
  • “k”桶

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

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

类型 2：

所以最快的排序方法是分配151个链表（我们称它们为桶）并根据每个人的年龄将每个人的数据结构放入桶中：

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

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

当你想在桶中插入一些东西时，你可以这样做：

  • 对桶（例如 LinkedList）进行二分查找以找到正确的位置
  • 插入元素

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

问题：

  1. 简单的说; 这是一种线性排序，因为排序需要线性时间。类型 1 和类型 2 都采用 O(n + k)。另一个需要考虑的重要因素是桶排序用于对每个单独的桶进行排序的子算法。如果使用快速排序，与例如冒泡排序相比，它将导致另一个下限。也可以选择具有不同边界的非比较子算法。子算法的良好选择和桶上的分布使得桶排序不限于 O(n(log n)) 下限。请记住，O-notation 不能保证速度，它可以保证增长率。如果您的输入大小从“N”翻倍到“2N”，那么您的线性时间算法将比诸如气泡排序之类的 O(n^2)（更坏情况）算法更好地应对它。

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

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

于 2013-05-23T14:02:03.343 回答
1

桶排序是线性时间的，当每个桶都在线性时间排序时。“Type 1”和“Type 2”都是线性时间的，因为每个桶中的所有值都成对比较相等，不需要进一步排序。

后两个问题的答案是实际可行的。通常，您的标准库排序的作者已经确定了插入排序的适当截止值。我想桶排序的性能在很大程度上取决于相关的数据和内存子系统。

于 2013-05-23T13:37:22.960 回答
0

您描述的类型1和类型2实际上是相同的意思你有一个范围。是的，在这种情况下，它是线性时间复杂度，因为每个桶内不需要进一步排序。每个存储桶都包含一种类型的值。

于 2019-08-10T22:49:39.607 回答