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

Question

我想探讨我对桶排序的分析，如下所示
有许多方法可以实现桶排序。其中一些如下
类型1:
如果

时间： O（N）
空间： O（1）
类型2：

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

时间：O（N K）
空间：O（N K）

类型3（如Wikepedia所示类型2的变体）

函数nextSort是用于对每个存储桶进行排序的排序函数。如果使用插入排序，则将使用比最差排序为O（n^2）或合并排序，以便保持比O（nlgn）稳定的排序。

• 问题：
  1

我根据以下内容进行了分析：
Wikepedia
桶排序的复杂性怎么可能是O（nk）
1996年1月23日算法讲稿的设计与分析
http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort。htm
http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-23.html
如果我们使用链表实现bucket，那么bucket排序的复杂性如何
桶排序的最坏情况复杂性是什么？

Answer 1

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

Answer 2

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

对后两个问题的答案是实践中可行的。通常，标准库排序的编写器已确定插入排序的适当截止点。我认为bucket sort的性能在很大程度上取决于所讨论的数据和内存子系统。

Answer 3

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

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

空格：O（1）
我们可以为每个可能的元素设置桶，

这不矛盾吗？您将为每个可能的元素声明bucket，并且仍然保持O（1）；）

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

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

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

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

第2类：

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

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

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

当您想将某物插入桶中时，您可以执行以下操作：

• 在bucket（例如LinkedList）上进行二进制搜索以找到正确的位置

通过这种方式，您也不需要在之后对桶进行排序，因为所有内容都已排序。不是说这是个好主意，只是指出了可能性

问题：
1）简单地说；这是线性排序，因为如果排序需要线性时间。类型1和类型2都采用O（n k）。因为bucket排序不使用诸如quicksort、bubblesort等元素之间的比较。。。它不受O（n log n）下限的约束。请记住，O符号并不能保证速度，它保证了增长率。如果您的输入大小从'N'加倍到'2N'，您的线性时间算法将比例如O（N^2）算法（如冒泡排序）更好地处理此问题

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

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