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

Question

我想探讨一下我对桶排序的分析，如下所示。
\n桶排序的实现方式有很多种。其中一些如下。
\n类型 1:
\nif\xc2\xa0we\xc2\xa0know\xc2\xa0the\xc2\xa0range\xc2\xa0of\xc2\xa0our\xc2\xa0elements\xc2\xa0to\xc2\xa0be\xc2\xa0sorted,\xc2 \xa0we\xc2\xa0can\xc2\xa0set\xc2\xa0up\nbuckets\xc2\xa0for\xc2\xa0each\xc2\xa0possible\xc2\xa0element,\xc2\xa0and\xc2\xa0just\xc2\xa0toss\xc2\xa0elements\ xc2\xa0进入\xc2\xa0其\xc2\xa0对应的\xc2\xa0buckets。\xc2\xa0我们\xc2\xa0然后\n清空\xc2\xa0的\xc2\xa0buckets\xc2\xa0in\xc2\xa0order,\xc2\xa0and\xc2\ xa0the\xc2\xa0result\xc2\xa0is\xc2\xa0a\xc2\xa0sorted\xc2\xa0list.\n在\xc2\xa0实现\xc2\xa0这个\xc2\xa0算法，\xc2\xa0we\xc2\xa0can\xc2\xa0easily\ xc2\xa0use\xc2\xa0an\xc2\xa0array\xc2\xa0to\xc2\xa0代表\xc2\xa0our\xc2\xa0buckets,\xc2\xa0where\xc2\xa0the\xc2\xa0value\xc2\xa0at\neach\xc2\xa0array \xc2\xa0index\xc2\xa0将\xc2\xa0表示\xc2\xa0\xc2\xa0的编号\xc2\xa0的\xc2\xa0elements\xc2\xa0in\xc2\xa0\xc2\xa0对应的\xc2\xa0桶。\xc2\xa0If\ xc2\xa0we\xc2\xa0have\xc2\xa0integers\non\xc2\xa0the\xc2\xa0range [0..max],\xc2\xa0then\xc2\xa0we\xc2\xa0set\xc2\xa0up\xc2\xa0an\xc2 \xa0array\xc2\xa0of\xc2\xa0(max + 1)\xc2\xa0integers\xc2\xa0and\xc2\xa0初始化\xc2\xa0all\xc2\xa0the\xc2\xa0values\xc2\xa0to\nzero。\xc2\xa0We \xc2\xa0然后\xc2\xa0继续\xc2\xa0顺序\xc2\xa0到\xc2\xa0the\xc2\xa0unsorted\xc2\xa0array,\xc2\xa0reading\xc2\xa0the\xc2\xa0value\xc2\xa0of\xc2\xa0each\ xc2\xa0element,\xc2\xa0going\n到\xc2\xa0的\xc2\xa0对应的\xc2\xa0index\xc2\xa0in\xc2\xa0the\xc2\xa0buckets\xc2\xa0array,\xc2\xa0和\xc2\xa0递增\xc2\ xa0\xc2\xa0值\xc2\xa0那里。

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

函数nextSort是一个排序函数，用于对每个桶进行排序。如果使用插入排序，那么最坏的时间复杂度为 O(n^2)，或者使用合并排序，这样我就可以保持 O(nlgn) 的稳定性。

\n\n

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

\n\n

我根据以下内容进行了分析：
\n维基百科
\n桶排序的复杂度怎么可能是 O(n+k)？
\n算法的设计与分析\n1996 年 1 月 23 日讲义
\n http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
\n http://cs.nyu.edu/courses/fall02 /V22.0310-002/lectures/lecture-23.html
\n如果我们使用链表实现桶，那么桶排序的复杂度是 O(n+k) 吗？
\n桶排序最坏情况的复杂度是多少？

\n

Answer 1

类型 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 表示法并不能保证速度，它只能保证增长率。如果您的输入大小从“N”翻倍到“2N”，您的线性时间算法将比诸如冒泡排序之类的 O(n^2)（最坏情况）算法更好地处理它。

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

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

Answer 2

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

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