求助一道算法分析题目,关于时间复杂度的
已知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),缺点是必须要求数的范围比较小，如果数的范围很大的话，就必须开很大的数组。
