桶排序创建 k 个桶....并在其中一个桶中分配 n 个数字.. 例如1-10， 11-20, 21-30... O(n+k)
桶中的编号使用插入 O(n²) 排序
当少数数字最终出现在同一个桶中时，它工作正常.. O(n+k) 但是如果所有的数字都在同一个桶中...O(n²)
我的问题是我们是否将桶的范围设置为 1，即 0-1 ,1-2, 2-3..... 不同的号码不会在同一个桶中结束....(不需要在桶内排序) O(n+k)
在不考虑空间复杂度的情况下，为什么我们不用这个来代替计数排序呢？ 如果我错了请纠正我..
最佳答案
您提出的是一种称为计数排序 的分布排序，只是一个更简单的版本，您知道元素不会重复，因此计数会停止在 1。它在 O(N+n) 时间上非常高效，但确实需要 O(N) 空间。
许多人在被要求对一副牌进行排序时自然会使用这种方法:他们会将每张牌分配到桌面上的位置，以形成 4 行，每行 13 张牌。最后一步是逐行收集卡片。这里我们有 N == n，因为这两个步骤都需要 O(n) 时间，所以排序非常有效。
当 N 变得比 n 大得多时，假设您想按序列号的顺序对一堆 20 美元的钞票进行排序，这种方法就变得完全不切实际。
如果您要对整数进行排序，您可能会考虑另一种时间复杂度为 O(n) 的方法:基数排序。
关于algorithm - 桶排序 :Why don't we set range to 1? vs 计数排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30561593/