在桶排序期间有跳过空桶的方法吗？
在桶排序期间有跳过空桶的方法吗？
提问于 2011-08-31 22:33:48
计数排序是一种桶式排序。假设我们是这样使用它的：
- 设
A是排序 - 的数组
k是最大元素 -
bucket[]是一个桶H 29H 110让每个桶都是一个链表(带有开始和结束指针)H 211F 212
然后在伪代码中，计数排序如下所示：
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)中有一种方法(不是简单，而是一种方法)来实现init数组。
2,3) O(n)
4,5) O(k)
6) O(n)
这给出了O(k+n)的净运行时，对于k >> n是Ω(n)，这对我们是不利的。但是，如果我们可以更改第4行5以某种方式跳过空桶呢？这样，我们最终会得到O(n)，没有金属，什么是k。
有人知道怎么做吗？还是不可能？
回答 2
Stack Overflow用户
发布于 2011-08-31 22:42:08
一种选择是持有一个包含实际使用的桶的辅助BST。每当您向桶中添加某些内容时，如果它是放置在桶中的第一个条目，您也会将该桶的值添加到BST中。
当您想要连接所有东西时，您可以按排序顺序遍历BST，只将找到的桶连接起来。
如果有实际使用的z桶，则需要O(n +z log )。如果桶的数量比实际使用的数量大，这可能要快得多。
更一般地，如果您有一种方法对O(f(z))时间中使用的z个不同的桶进行排序，则可以在O(n + f(z))时间内进行桶排序。维护实际使用的桶的第二个数组，在第一次使用时将桶添加到数组中。在迭代桶之前，在O(f(z))中对桶的索引进行排序，然后遍历该数组来确定要访问的桶。例如，如果使用y-快速树，则可以在O(n +z日志日志z)中进行排序。
希望这能有所帮助！
Stack Overflow用户
发布于 2011-08-31 22:44:49
您可以将桶数组转换为关联数组，从而产生O(n log )，我认为您不能比排序(平均)做得更好。
O(n)在一般情况下是不可能的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7264264
复制相关文章
相似问题
腾讯云开发者
