如何在线性排序下考虑桶排序？
我想探索我的分析关于桶的排序如下。
可以通过多种方式实现桶排序。其中一些建议如下。
1型：
如果我们知道的话，如果我们知道的话，再把再加工的基本元素的范围进行分类，就可以为每一种可能的亚型产品建立类似的产品桶，然后再按顺序空出相关的产品，结果是一个分类的产品清单。在实现该算法时，我们可以很容易地使用一个新的子阵列来表示我们的子桶，其中每个子阵列上的值将表示对应桶中的子元的数目。然后，如果我们在每个子桶上都有相应的码元，那么我们就可以在每个子桶中读取相应的码元。如果我们有一个(max+1)的子元阵列，那么就先将每个子元的值初始化为零。然后，我们通过对每个子桶进行码元分解，读取每个元的码元值，再到相应的码桶中的码元，然后再把它的值增加到零。
时间: O(N)
空间: O(1)
2型：
按年龄对一组人进行排序
对于排序，年龄与任意整数略有不同。正因为如此，它有一个小范围的0-150。因此，排序的最快方法是分配151个链接列表(我们称之为桶)，并根据每个人的年龄将每个人的数据结构放入桶中：
时间: O(N+K)
空间: O(N+K)
维基百科) 3型( type2的变异，见)
函数nextSort是一个排序函数，用于对每个桶进行排序。如果插入排序比最坏使用的排序更糟，则使用O(n^2)或合并排序，这样我就可以保持比O(nlgn)更稳定的状态。
- 问题： 1>How它被认为是线性排序，是因为类型1还是类型2？ 2>If，我使用类型3像WIkepedia，哪种排序是有效的，每个桶排序？ 我知道在实践中使用插入排序的原因是，我们期望桶很小，而对于小列表，插入排序要比其他任何东西都快得多。即使在实现合并排序或快速排序时，当列表变得足够小时也会使用插入排序(例如在以下20项左右)。 3>for类型3我可以在哪一个基础上决定桶的范围？ 这一点很重要，因为如果尝试使用大量桶(例如大于n )进行桶排序，运行时可能会被扫描所有桶以寻找实际使用的桶所需的时间所支配，即使其中大多数是空的。
我分析的基础是：
1996年1月23日算法讲稿的设计与分析
http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
http://cs.nyu.edu/courses/fall02/V22.0310-002/lectures/lecture-23.html
回答 3
Stack Overflow用户
发布于 2013-05-23 14:02:03
第1类：
您所描述的第一种类型并不是真正的桶排序。它实际上是在计数排序或关键索引计数。尽管它被认为是桶排序的一个变体。原因在于您实际上只是在计算每个键的出现情况，而不是将密钥本身存储在桶中。
参考文献：排序
参考文献：http://www.cs.princeton.edu/courses/archive/spr13/cos226/demo/51DemoKeyIndexedCounting.pdf
空间: O(1) 我们可以为每一个可能的元素设置桶，
这不是矛盾吗？您将为每个可能的元素声明桶，并且仍然保留O(1)？)
如果您希望算法是稳定的，您也不能覆盖输入数组。因此，在实践中，您需要n+k的空间要求：
- 长度'n‘的输出数组(与输入数组的大小基本相同)
- 'k‘桶
如果您检查用于计数排序的伪代码，您将注意到最后一个循环再次遍历输入数组，以查看每个元素需要去哪里。通过按照它们在输入数组中的出现顺序进行排序，您将得到一个稳定的排序。
PS:记住，你不一定要对整数进行排序。如果输入是an之间的字符数组，也可以使用此算法。
第2类：
因此，排序的最快方法是分配151个链接列表(我们称之为桶)，并根据每个人的年龄将每个人的数据结构放入桶中：
这可能是最简单的方法，因为您可以找到所需的桶相当容易，但这不一定是最快的方式。例如，另一种可能是每10年创建一次桶。
00 - 09
10-19
20 - 29
..。
当你想把什么东西插入桶里时，你可以：
- 对桶(例如LinkedList)进行二进制搜索以找到正确的位置
- 插入元素
这样，您也不需要在事后对桶进行排序，因为所有的东西都已经排序了。不是说这是个好主意，只是指出了可能性。
问题：
- 简单地说，这是一个线性排序，因为排序需要线性时间。类型1和类型2都取O(n + k)。要考虑的另一个重要因素是桶排序用于对每个单独桶进行排序的子算法。如果使用快速排序，它将产生另一个下限，例如，与bubblesort相比。还可以选择不同边界的非比较子算法。子算法的一个很好的选择和桶上的分布使桶排序不局限于O(n(log ))下界。请记住，O-表示法没有给出任何关于速度的保证，它提供了增长率的保证。如果您的输入大小从'N‘增加到'2N’，您的线性时间算法将比像bubblesort这样的O(n^2) (更坏的情况)算法更好地处理它。
- 插入排序对于小型数组确实是有效的，这也是选择它的主要原因。再加上它是稳定的。因为如果不使用稳定的算法对桶本身排序，整个算法(桶排序)就不会稳定。
- 很难说。这取决于我认为的数据。如果您必须对100万32位整数进行排序，则不会为它们创建2^32个桶。在这种情况下，最好看看其他算法(例如，LSD基排序)，这些算法将基本创建9个桶(每个数字为1个)。
Stack Overflow用户
发布于 2013-05-23 13:37:22
桶排序是线性时间，当每个桶按线性时间排序时。“类型1”和“类型2”都是线性时间，因为每个桶中的所有值成对比较相等，不需要进一步排序。
对后两个问题的答案是，无论在实践中起什么作用。通常，标准库排序的作者已经为插入排序确定了适当的截止点。我设想桶排序的性能在很大程度上取决于所讨论的数据和内存子系统。
Stack Overflow用户
发布于 2019-08-10 22:49:39
您所描述的类型1和类型2实际上是相同的，这意味着您有一个范围。是的，在这种情况下，它的线性时间复杂性，因为不需要进一步排序是在每个桶。每个桶包含一种类型的值。
https://stackoverflow.com/questions/16713702
复制相似问题
腾讯云开发者
