在计数排序算法中使用额外数组并计算较小元素的原因

Question

在确定输入数组中每个元素的频率后，仅利用计数数组（

C

）来简化计数排序算法是否可行？我们是否可以通过逆序遍历

C

并相应地放置元素来直接实现排序数组，而不是创建额外的输出数组？例如，如果我们有一个输入数组

A

和相应的计数数组

C

:

通过在末尾放置一个 5、后面没有 4、在 5 之前放置三个 3、添加两个 2、最后没有 1 和两个 0 来对数组进行排序是否有效？这将导致排序数组：

此外，在现有的计数排序实现中，我们计算

C

中的每个元素与其前一个元素的总和，以确定有多少元素低于或等于该特定元素。考虑到这一点，我们是否可以仅依靠

C

中的累积计数来简化排序过程，并消除涉及创建额外输出数组和向前遍历输入数组的传统步骤？除了稳定性和输入数组元素代表对象属性（例如卫星数据）的场景等考虑之外，是否还有理由保留现有流程？

Answer 1

在确定输入数组中每个元素的频率后，仅利用计数数组（C）来简化计数排序算法是否可行？我们是否可以通过逆序遍历C并相应地放置元素来直接实现排序数组，而不是创建额外的输出数组？

如果排序键是正在排序的项目本身，这是正常的，在这种情况下，从前到后遍历数组也同样有效（并且更容易编码）。否则，不，它不起作用，出于同样的原因，从前到后做同样的事情不起作用：除非对象已经按顺序排列，否则您将覆盖并丢失其中一些。

此外，在现有的计数排序实现中，我们计算 C 中每个元素与其前一个元素的总和，以确定有多少元素低于或等于该特定元素。 [...]我们可以通过仅依靠 C 中的累积计数来简化排序过程，并消除涉及创建额外输出数组和向前遍历输入数组的传统步骤吗？

当项目本身是键时，您可以执行这种简化。否则不会，因为如果您不使用额外的存储空间，您将再次覆盖并丢失一些项目。

除了稳定性和输入数组元素代表对象属性（例如卫星数据）的场景等考虑之外，是否还有理由保留现有流程？

同样，在对整数进行排序的特殊情况下，可以简化计数排序，其中项本身就是排序键。也许在其他一些特殊情况下也是如此。然而，一般来说，您需要额外的步骤和存储才能获得正确的结果。

您还可以考虑将计数排序转换为Flash排序，它会就地重新排序数组，但这并不是一个简化。