更改计数排序算法

Question

这是一个计数排序算法。我想把它的最后一个for循环改为for j<---1 to n。我知道这将是正确的，但我想向我的一个朋友展示这个。我该如何写出我的理由呢？请帮帮我!谢谢。

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

Answer 1

以上代码是完全正确的。如果更改1 to n的最后一个循环，输出将是正确的，但具有相同值的元素的相对顺序将颠倒。例如，如果原始数组只包含3个元素，并且所有元素都设为5，那么在1 to n的情况下，最后5个元素将是第一个元素，第二个倒数5个元素将是第二个元素，前5个元素将是最后一个元素，即相同元素的相对顺序颠倒。

Answer 2

不，最后一个循环应该是n downto 1，因为这会导致排序为stable sort (即，如果两个元素相等，它们将保持其原始顺序)。

如果将其更改为1 to n，则列表中所有相等的子序列将被放入相反的顺序。有时这并不重要，但有时确实如此，既然使用n downto 1没有任何缺点，那么应该优先使用它。