0

AFAIK计数排序使用以下算法：

// A: input array
// B: output array
// C: counting array
sort(A,B,n,k)
1. for(i:k) C[i]=0;
2. for(i:n) ++C[A[i]];
3. for(i:k) C[i]+=C[i-1];
4. for(i:n-1..0) { B[C[A[i]]-1]=A[i]; --C[A[i]]; }

我删除第 3 步和第 4 步，然后执行以下操作呢？

3. t=0; for(i:k) while(C[A[i]]) { --A[i]; B[t++]=i; }

完整的代码在这里，看起来不错，但我不知道哪个有更好的性能。

问题：

  1. 我猜这两个版本的复杂性是一样的，是这样吗？
  2. 在第 3 步和第 4 步中，第一个版本需要迭代 n+k 次，第二个版本只需迭代 n 次。那么第二个性能更好吗？
4

1 回答 1

1

您的代码似乎是正确的，它可以在对数字进行排序的情况下工作。但是，假设您有一个结构数组，您正在根据它们的键对其进行排序。在这种情况下，您的方法将不起作用，因为它只是计算数字的频率，并且在保持正数的同时将其分配给输出数组中增加的索引。然而，经典方法适用于结构和对象的数组等，因为它计算每个元素应该去的位置，然后将数据从初始数组复制到输出数组。

要回答您的问题：

n1> 是的，您的代码的运行时复杂度将是相同的，因为对于 size和 range的数组0...k，您的内部和外部循环运行与 成比例f(0)+f(1)+...+f(k)，其中 f 表示数字的频率。因此运行时间为 O(n)。

2>就渐近复杂度而言，两种方法具有相同的性能。由于额外的循环，常数可能更高。但是，这也使经典方法成为一种稳定的排序，并具有我之前指出的好处。

于 2013-08-27T11:10:42.240 回答