algorithm - 桶排序 :Why don't we set range to 1? vs 计数排序

Question

桶排序创建 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)

在不考虑空间复杂度的情况下，为什么我们不用这个来代替计数排序呢？如果我错了请纠正我..

Answer 1

您提出的是一种称为计数排序 的分布排序，只是一个更简单的版本，您知道元素不会重复，因此计数会停止在 1。它在 O(N+n) 时间上非常高效，但确实需要 O(N) 空间。

许多人在被要求对一副牌进行排序时自然会使用这种方法:他们会将每张牌分配到桌面上的位置，以形成 4 行，每行 13 张牌。最后一步是逐行收集卡片。这里我们有 N == n，因为这两个步骤都需要 O(n) 时间，所以排序非常有效。

当 N 变得比 n 大得多时，假设您想按序列号的顺序对一堆 20 美元的钞票进行排序，这种方法就变得完全不切实际。

如果您要对整数进行排序，您可能会考虑另一种时间复杂度为 O(n) 的方法:基数排序。