计数排序 - 为什么在插入过程中要逆序排列？

Question

我在GeeksForGeeks上查看计数排序的代码上的计数排序代码，在算法的最后阶段，原始数组中的元素被插入到排序数组中的最终位置（倒数第二个 for 循环），输入数组以相反的顺序遍历。

我似乎无法理解为什么你不能从输入数组的开头到结尾，如下所示：

for i in range(len(arr)): 
        output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] 
        count_arr[arr[i] - min_element] -= 1

是否有一些我错过的以相反顺序进行的微妙原因？如果这是一个非常明显的问题，我深表歉意。我在这里也看到了以相同风格实现的计数排序。

任何评论都会有帮助，谢谢！

Answer 1

稳定。按照你的方式，等值元素的顺序会被颠倒而不是保留。向后检查输入会取消向后复制（那个-= 1东西）。