计数排序范围是否始终需要在 [0,k] 内？
我可以对一个巨大的数字池中的一小部分数字（例如 A=[7,9,12,15]）进行计数排序，我知道该数字池仅包含小数组中的数字吗？或者小范围总是必须是[0..k]。
我可以通过说 [0..15] 对数组 A 进行计数排序，但这没有意义。 如果 A=[100,750,452] 呢？
所以我认为这是可行的。 我想要一些意见。
Can I do a counting sort on a small range of numbers say A=[7,9,12,15] from a huge pool of numbers, which I know will consist of only the numbers in the small array? Or does the small range always have to be [0..k].
I can do counting sort on the array A by saying [0..15] but it does not make sense.
And what if A=[100,750,452]
So I guess it is feasible.
I would like some inputs please.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你的问题不是很清楚，但就这样吧。从您的示例中 A=[7,9,12,15] 范围为 [0..15] 并且需要大小为 k=15 的附加空间（以及 A[length] 的另一个结果数组。由于 n (A[length ]) 是 4，总体运行时间将为 theta(k + n)。计数排序是一种“时空权衡”算法，但如果在您的情况下使用，则没有任何意义。当你有 k=Big-O(n) 时，应该使用计数排序，这意味着 A[] 中的最大值小于 A[] 的大小，我相信该算法仍然会对你的示例进行排序。正确。
Your question isn't very clear, but here it goes. From your example A=[7,9,12,15] the range be [0..15] and would require addition space of size k=15 (and another result array of A[length]. Since n (A[length]) is 4, the overall runtime would be theta(k + n). Counting sort is a "space-time tradeoff" algo, but if used in your case it wouldn't make any sense. Since, there isn't any tradeoff. Counting sort should be use when you have k=Big-O(n), which means the maximum value in your A[] is less than the size of A[]. btw, I believe the algorithm would still sort your example correctly.