为什么我不能用这种方式进行计数排序?
Why can't I do the counting sort this way?
计数排序基本上是将计数值存储在哈希-table 排序结构中,然后打印出这些值。
我采用的方法是:
遍历输入数组并按count[arr[i]]++
存储总计数
再次遍历计数数组并打印 i(th)
索引号与 count[arr[i]]
中的值一样多的次数。这不是正确的方法吗?
我阅读教程的大部分地方,他们将前面元素的计数之和存储在计数数组中,然后通过先减少计数然后打印它来放置在排序数组中。
我的方法有问题吗?
谢谢!
当比较相同的数组中的所有对象都相同时,您的方法就可以了。例如,在数组 [ 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 的前缀和,它将算法概括为对可能不同但比较相等的对象进行操作,因此它打印一次火龙果和一次西瓜。
Wikipedia 页面的 Variant algorithms 部分的计数排序提到了您的优化,说当排序的项目是整数时,可以合并第二个和第三个循环。
计数排序基本上是将计数值存储在哈希-table 排序结构中,然后打印出这些值。
我采用的方法是:
遍历输入数组并按
count[arr[i]]++
存储总计数
再次遍历计数数组并打印
i(th)
索引号与count[arr[i]]
中的值一样多的次数。这不是正确的方法吗?
我阅读教程的大部分地方,他们将前面元素的计数之和存储在计数数组中,然后通过先减少计数然后打印它来放置在排序数组中。
我的方法有问题吗?
谢谢!
当比较相同的数组中的所有对象都相同时,您的方法就可以了。例如,在数组 [ 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 的前缀和,它将算法概括为对可能不同但比较相等的对象进行操作,因此它打印一次火龙果和一次西瓜。
Wikipedia 页面的 Variant algorithms 部分的计数排序提到了您的优化,说当排序的项目是整数时,可以合并第二个和第三个循环。