求助一道算法分析题目,关于时间复杂度的
已知n个互不相同的正整数Si,1 <=i <=n,1 <=Si <=n

问是否存在一个排序算法,使得时间复杂度为O(n)

以下是我的算法,我认识是有的

void insert(int S[i],int Q[n])

//S[i]是要排序的数组,Q[n]是一个有n个元素的数组

{

int k,m;

m=0;

for(k=0;k <n;k++)

Q[k]=0;

for(k=0;k <i;k++)

Q[S[k]]=1;

for(k=0;k <n;k++)

{

if(Q[k]==1){

S[m]=k;

m++;

}

我不知道对不对,我的想法是这样的

比如n=10;要排序的数组为S[4]={7,3,8,2}

这样得到一个数组Q[10]={0,0,1,1,0,0,0,1,1,0}



[解决办法]
对呀，这就是著名的桶排序，优点是时间复杂度为o(n),缺点是必须要求数的范围比较小，如果数的范围很大的话，就必须开很大的数组。