有没有办法在桶排序时跳过空桶？
计数排序是一种桶排序。假设我们像这样使用它：
- 设
A为要排序的数组 - 设
k为最大元素 - 设
bucket[]为桶数组 - 让每个桶都是一个链表（带有开始和结束指针）
然后在伪代码中，计数排序如下所示：
Counting-Sort (A[], bucket[], k)
1. Init bucket[]
2. for i -> 1 to n
3. add A[i] to bucket[A[i].key].end
4. for i -> 1 to k
5. concatenate bucket[i].start to bucket[0].end
6. bucket[0].end=bucket[i].end
7. copy bucket[0] to A
按行计算时间复杂度：
1）我知道有一种方法（不是简单但一种方法）来初始化数组O(1)
2,3) O(n)
4,5) O(k)
6) O(n)
这给出了 O(k+n) 的净运行时间，对于 k >>> n 是 Ω(n)，这对我们不利。但是如果我们可以更改第 4,5 行以某种方式跳过空桶呢？这样，无论 k 是什么，我们最终都会得到 O(n) 的结果。
有谁知道该怎么做？或者说这是不可能的？
Counting sort is kind of a bucket sort. Let's assume we're using it like this:
- Let
Abe the array to sort - Let
kbe the max element - Let
bucket[]be an array of buckets - Let each bucket be a linked list (with a start and end pointer)
Then in pseudocode, counting sort looks like this:
Counting-Sort (A[], bucket[], k)
1. Init bucket[]
2. for i -> 1 to n
3. add A[i] to bucket[A[i].key].end
4. for i -> 1 to k
5. concatenate bucket[i].start to bucket[0].end
6. bucket[0].end=bucket[i].end
7. copy bucket[0] to A
Time Complexity by lines:
1) I know there is a way (not simple but a way) to init array in O(1)
2,3) O(n)
4,5) O(k)
6) O(n)
This gives us a net runtime of O(k+n), which for k >> n is Ω(n), which is bad for us. But what if we can change lines 4,5 to somehow skip the empty buckets? This way we will end up having O(n) no metter what k is.
Does anyone know how to do this? Or is it impossible?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一种选择是保存一个辅助 BST，其中包含实际使用的存储桶。每当您向存储桶中添加某些内容时，如果它是放置在那里的第一个条目，您还会将该存储桶的值添加到 BST 中。
当您想要连接所有内容时，您可以按排序顺序迭代 BST，仅连接您找到的存储桶。
如果实际使用了 z 个存储桶，则需要 O(n + z log z)。如果桶的数量比实际使用的数量大，这可能会快得多。
更一般地说，如果您有一种方法可以在 O(f(z)) 时间内对正在使用的 z 个不同存储桶进行排序，则可以在 O(n + f(z)) 时间内进行存储桶排序。维护您实际使用的存储桶的第二个数组，在第一次使用时将存储桶添加到该数组中。在迭代存储桶之前，以 O(f(z)) 时间对 usem 中的存储桶索引进行排序，然后迭代该数组以确定要访问哪些存储桶。例如，如果您使用 y-Fast 树，则可以按 O(n + z log log z) 进行排序。
希望这有帮助！
One option would be to hold an auxilary BST containing which buckets are actually being used. Whenever you add something to a bucket, if it's the first entry to be placed there, you would also add that bucket's value to the BST.
When you want to then go concatenate everything, you could then just iterate over the BST in sorted order, concatenating just the buckets you find.
If there are z buckets that actually get used, this takes O(n + z log z). If the number of buckets is large compared to the number actually used, this could be much faster.
More generally - if you have a way of sorting the z different buckets being used in O(f(z)) time, you can do a bucket sort in O(n + f(z)) time. Maintain a second array of the buckets you actually use, adding a bucket to the array when it's used for the first time. Before iterating over the buckets, sort in O(f(z)) time the indices of the buckets in usem then iterate across that array to determine what buckets to visit. For example, if you used y-Fast trees, you could sort in O(n + z log log z).
Hope this helps!
您可以将存储桶数组转换为关联数组，这会产生 O(n log n)，并且我不相信您可以做得比排序更好（在平均的）。
O(n) 在一般情况下是不可能的。
You can turn the bucket array into an associative array, which yields O(n log n), and I don't believe you can do better than that for sorting (on average).
O(n) is impossible in the general case.