algorithm - 线性时间排序

Question

我需要编写一个算法来对大小为 [0..N-1] 的数组进行排序，该数组填充了 [0..N-1] 范围内的值。数组中的值不能重复。排序应该在线性时间内进行，我只允许使用一些额外的变量。

请评论我写的代码。据我猜测，最坏的时间是 2*N。还是线性时间？有没有可能让速度更快？

public int sort(){
    int i  = 0;             
    while (i < n){
        if (a[i] != i)      
            switchElements(a[i], a[a[i]]);                  
        else
            i++;                    
    }
    return count;
}

另外 1 我真的需要对数组进行排序，因为排序只是任务的一部分。完整的任务是在线性时间内查找数组中是否存在重复值，并且没有其他变量。

Answer 1

原始问题的答案:

包含[0..N-1]元素的数组，包含不重复元素[0..N-1]

为什么还要排序？排序后的数组已知并且是[0..N-1]。

---

考虑到您的额外 1:您的算法看起来不错，您正在查看每个元素一次，并且必须至少查看每个元素一次，因此它不会变得更好。此外，2*N 也是 O(N)。