Bucket sort:Why 我们不将范围设置为 1 吗？与计数排序
Bucket sort:Why don't we set range to 1? vs counting sort
桶排序创建 k 个桶....并在其中一个桶中分配 n 个数字..
例如1-10，
11-20,
21-30...
O(n+k)
桶中的 no.s 使用插入排序 O(n²)
当少数数字最终出现在同一个桶中时它工作正常.. O(n+k)
但是如果所有数字都在同一个桶中...O(n²)
我的问题是我们是否将桶的范围设置为 1，即 0-1
,1-2,
2-3.....
不同的 no.s 不会在同一个桶中结束....（不需要在桶内排序）
O(n+k)
在不考虑 space 复杂性的情况下，为什么我们不使用它来代替计数排序？
如果我错了请指正我..
k 的值在第一种方法和你提出的方法中是不一样的。假设您有 n 个介于 0 和 N 之间的数字。在第一种情况下（大小为 10 的桶）您需要 N/10 个桶，在第二种情况下（大小为 1 的桶）需要 N 个桶。根据 N 和 n 的相对值，k 的最优值可能不是 k=1。
您提出的是一种名为 count sort 的分布排序，只是一个更简单的版本，您知道元素不重复，因此计数在 1 处停止。它在时间上非常有效 O(N+n) 但确实需要 O(N) space.
许多人在要求对一副纸牌进行排序时自然会使用这种方法：他们将每张纸牌分配到其在 table 上的位置，以形成 4 行，每行 13 张纸牌。最后一步是逐行收集卡片。这里我们有 N == n，因为这两个步骤都需要 O(n) 时间，所以排序非常有效。
当N变得比n大得多时，假设你想按照序列号的顺序对一堆20美元的钞票进行排序，这种方法就变得完全不切实际了。
如果您要对整数进行排序，您可以考虑另一种具有 O(n) 时间复杂度的方法：基数排序。
桶排序创建 k 个桶....并在其中一个桶中分配 n 个数字.. 例如1-10， 11-20, 21-30... O(n+k)
桶中的 no.s 使用插入排序 O(n²)
当少数数字最终出现在同一个桶中时它工作正常.. O(n+k) 但是如果所有数字都在同一个桶中...O(n²)
我的问题是我们是否将桶的范围设置为 1，即 0-1 ,1-2, 2-3..... 不同的 no.s 不会在同一个桶中结束....（不需要在桶内排序） O(n+k)
在不考虑 space 复杂性的情况下，为什么我们不使用它来代替计数排序？ 如果我错了请指正我..
k 的值在第一种方法和你提出的方法中是不一样的。假设您有 n 个介于 0 和 N 之间的数字。在第一种情况下（大小为 10 的桶）您需要 N/10 个桶，在第二种情况下（大小为 1 的桶）需要 N 个桶。根据 N 和 n 的相对值，k 的最优值可能不是 k=1。
您提出的是一种名为 count sort 的分布排序，只是一个更简单的版本，您知道元素不重复，因此计数在 1 处停止。它在时间上非常有效 O(N+n) 但确实需要 O(N) space.
许多人在要求对一副纸牌进行排序时自然会使用这种方法：他们将每张纸牌分配到其在 table 上的位置，以形成 4 行，每行 13 张纸牌。最后一步是逐行收集卡片。这里我们有 N == n，因为这两个步骤都需要 O(n) 时间，所以排序非常有效。
当N变得比n大得多时，假设你想按照序列号的顺序对一堆20美元的钞票进行排序，这种方法就变得完全不切实际了。
如果您要对整数进行排序，您可以考虑另一种具有 O(n) 时间复杂度的方法：基数排序。