关于计数排序算法

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改为这个：for j<--1 to n，算法也会正确吗？(有什么方法可以证明这个"for“算法是正确的吗？)

同样，在这种情况下，算法也是稳定的？

谢谢

Answer 1

算法在两方面都是正确的。它也是稳定的，就像你现在拥有的一样。

如果您将最后一个for更改为您所说的内容，它将不再稳定。

基本上，在第三个for循环结束后执行C[i] = how many elements <= i exist。因此，C[A[j]]按照排序顺序提供值为A[j]的元素的最后一个位置，C[A[j]] - 1为值为A[j]的元素的倒数第二个位置，依此类推。这就是您递减C中的值的原因。

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

Answer 2

好的，简单解释一下算法：

1. for loop:用0和大小k(整数的范围)初始化C数组
2. for loop:计算整数并将数字存储在C
3. for loop中:将值的总数加起来等于给定的一个示例:有5个1，3个2，2个3 => c1 = 5，c2 = 8，c3 = 10
4. for loop:从A数组的末尾开始，将其放入B值中的相应C值，然后减少C

<>G29中的值

因为您将不同数字的最后一个位置存储在C数组中，所以还必须从A数组的末尾开始。如果你只处理整数，如果你从j<--1到n开始，算法也是正确的

没有给出稳定性:例如，1将处于逆序

示例：(我将索引添加到一次，两次显示顺序)

A1a，2，1b

第一个for循环

• C1 = 0
• C2 = 0

第二个for循环

j=1: A1 = 1a

C[1] = 1
C[2] = 0

j=2: A2=2

C[1] = 1
C[2] = 1

j=3: A3=1b

C[1] = 2
C[2] = 1

第三个for循环

C2 =3

第四个for循环

j=1 b2=1a c1=1

j=2 b3=2 c2=2

j=3 b1=1b c1=0

结果：

• b1 = 1b
• b2 = 1a
• b3 = 2

=>不稳定

Answer 3

在我看来，算法似乎是稳定的。

如果你改变了最后一个for，那么它仍然是正确的，但是不稳定。(将颠倒相等元素的顺序)。