为什么我不能以这种方式进行计数排序？

Question

计数排序基本上是将计数值存储在哈希表排序结构中，然后打印出这些值。

我采用的方法是:

1. 遍历输入数组并存储count[arr[i]]++

的总计数。

2. 再次遍历count数组并打印i(th)索引号，次数与count[arr[i]]中的值相同。这不是正确的方法吗?

在我阅读教程的大多数地方，他们都将前面元素的计数总和存储在count数组中，然后通过先减少计数然后打印它来放置在排序数组中。

我的方法有什么问题吗?

谢谢!

Answer 1

当数组中比较相同的所有对象都相同时，您的方法是好的。例如，在数组[ 8, 2, 3, 5, 4, 3 ]中，两个3都是相同的，因此在排序结果中打印两次哪个3并不重要。但是考虑下面的JSON数组:

[
    { "name": "apple", "quantity": 8 },
    { "name": "banana", "quantity": 2 },
    { "name": "dragonfruit", "quantity": 3 },
    { "name": "kiwifruit", "quantity": 5 },
    { "name": "pineapple", "quantity": 4 },
    { "name": "watermelon", "quantity": 3 }
]

如果你按数量排序这个数组，火龙果和西瓜将被放在同一个箱子里，3。但是，当循环遍历这些箱子时，不能只打印两次火龙果来生成排序结果。相反，通过在算法中间插入一个循环来计算每个bin的前缀和，它将算法推广到对可能不同但比较为相等的对象进行操作，因此它打印一次火龙果，打印一次西瓜。

维基百科页面计数排序的变体算法部分提到了你的优化，说当排序的项是整数时，第二个和第三个循环可以组合。