为什么我们在使用计数排序时要向后遍历

Question

我已经使用计数排序几天了。我注意到我们在使用它时会向后移动。我想知道为什么？如果有人能回答，那就太好了。

Answer 1

我们这样做是为了保持稳定性，因为如果我们遍历1 4 1 2 7 2因为1的频率是2，如果我们从前面穿过，它会先移动一个到第二个位置，然后再次移动三个到第一个位置，扰乱它们的顺序。如果我们认为这两个相同，这不会有太大影响，但如果我们使用2D阵列，并且有一些数据附在它上，这会影响，如果从前面穿过的话，这会改变顺序，你自己在纸上试一下，你就会明白记住顺序。

Answer 2

计数排序背后的基本思想如下：

1. 为原始数组构建一个频率直方图，说明每个元素出现的次数
2. 在直方图上循环，写出每个元素的适当副本数

有很多方法可以将这个概念性的想法转化为代码。您共享的链接通过以相反的顺序迭代直方图来完成步骤(2(，但您需要这样做并没有什么深层原因。您可以很容易地以正常的从低到高的顺序迭代直方图，元素将重新排序。