sorting - 计数排序范围是否总是需要在 [0,k] 中？

Question

我可以对一小部分数字进行计数排序，比如 A=[7,9,12,15] 从一个巨大的数字池中，我知道这将只包含小数组中的数字吗？或者小范围总是必须是[0..k]。

我可以通过说 [0..15] 对数组 A 进行计数排序，但这没有意义。如果 A=[100,750,452]

所以我想这是可行的。我想要一些输入。

Answer 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[] 的大小。顺便说一句，我相信算法仍然会对你的例子进行排序正确。