按线性时间排序

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).