3

计数排序是一种桶排序。假设我们像这样使用它：

  • 设为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)。

有谁知道如何做到这一点？还是不可能？

4

2 回答 2

1

一种选择是保存一个辅助 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) 进行排序。

希望这可以帮助！

于 2011-08-31T22:42:08.953 回答
0

您可以将存储桶数组转换为关联数组，这会产生 O( n log n )，而且我认为您不能比排序做得更好（平均而言）。

在一般情况下O( n ) 是不可能的。

于 2011-08-31T22:44:49.110 回答