arrays - 为什么这个算法稳定，我怎么能让它不稳定？

Question

我问是出于兴趣，需要以某种方式了解如何知道算法是否稳定。

稳定是什么意思？ 如果两个具有相同键的对象出现在排序输出中的顺序与它们出现在要排序的输入数组中的顺序相同，则称排序算法是稳定的。

如果我对算法理解正确的话，数组中相等的元素不能分配给同一个数组，所以它是一个稳定的算法。

我怎样才能让它变得不稳定？我不想做很大的改变，将 for i = n down to 1 do 更改为 for i = 1 to n do 怎么样？ 我认为这应该是打破它的一种方式，但我不太确定 :D

Input: Array arr with n integers, from 1 to m
Output: Array arr sorted upwards

Initialize Array B with length m which is set to 0 everywhere
n <-- |arr|
Initialize Array C with length n
for i = 1 to n do
   B[arr[i] <-- B[arr[i]] + 1
end for
for j = 2 to m do
   B[j] <-- B[j] + B[j-1]
end for
for i = n down to 1 do
   C[B[arr[i]]] <-- arr[i]
   B[arr[i]] <-- B[arr[i]] - 1
end for
return C

这应该和上面的代码一样:

countingsort(A, k)
{
  C = array(0, k)
  for (m=0; m<=k; m=m+1)
    C[m] = 0
  // end for
  for (j=1; j<=A.size; j=j+1)
    C[A[j]] = C[A[j]] + 1
  // end for
  i=0
  B = array(1, A.size)
  for (m=0; m<=k; m=m+1)
    while ( C[m]>0 )
    { 
      B[i] = m
      i = i+1
      C[m]=C[m]-1
    } // end while
  // end for
  return B
}

Answer 1

这是一个计数/基数排序，具有单个字段，用于对从 n 到 1 的数组进行排序。将最后一个 for 循环切换为 1 到 n 会使其不稳定，因为相等的元素将以相反的顺序存储。