algorithm - 关于计数排序算法

Question

我读过一个计数排序算法，它是这样的:

Counting Sort(A[1,..n]) //C[1,...k] is the temporary memory and k is the range of integers
   for  i<-- 1 to k
      C[i]<-- 0
   for  j<-- 1 to n
      C[A[j]]<--C[A[j]]+1
   for  i<--2 to k
      C[i]<--C[i]+C[i-1]
   for  j<--n downto 1
      B[C[A[j]]]<--A[j]
      C[A[j]]<--C[A[j]]-1

我想知道如果我将最后一个更改为:for j<--1 to n ，算法也会正确吗？？？(有什么办法可以证明这个“for”算法是正确的？？？)

这样算法也稳定吗？

谢谢

Answer 1

该算法在两个方面都是正确的。它也很稳定，因为您现在拥有它。

如果你改变最后一个for按照你说的，它会停止稳定。

基本上，C[i] = how many elements <= i exist第三场结束后for环形。所以C[A[j]]为您提供值为 A[j] 的元素的最后位置按排序顺序，C[A[j]] - 1值为 A[j] 的元素的倒数第二个位置等等。这就是为什么要减少 C 中的值的原因.

因此，如果您关心稳定性，则必须开始以相反的顺序迭代原始数组:以便最后一个值为 x 的元素。在您的原始数组中首先放在新数组中。反向迭代原始数组将保证 x放在之后所有其他等于 x 的值，从而使算法稳定。