在O(n)时间内对序列进行排序

Question

可能重复:
按线性时间排序？

假设给出了一个n个元素的序列S,每个元素都是[0,n ^ 2-1]范围内的整数.我们可以在O(n)时间内对它进行排序吗？

请不要介意我问太多面试问题.我只是在说.

Answer 1

没有.

唯一的前提条件是0-N²范围内的整数.

• 计数排序将不起作用,因为扫描,无论是不同输入的位模式还是重复输入的存储区,都将在O(N²)中完成
• 该范围将使得基数排序的密钥长度取决于N,因此基数在O(N)中不起作用.

任何涉及"当N很小"的语句都会使任何基于O的参数无效.

Answer 2

如果有 n^2-1 位可用内存，只需扫描序列，将序列值索引的每个位设置为 1。即序列大小的 O(n)。随后，测试存在性是 O(1) 操作。

当然，如果你想把排序后的序列读出来，那就是O(n^2)，因为你需要扫描整个n^2-1位的集合来寻找1。