UC知道求助一道算法分析的题目
来源：百度知道 编辑：UC知道 时间：2024/05/09 20:23:45
已知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)
以下是我的算法,我认识是有的
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}
这类方法在需要排序的数组的长度比较大而数组中的数可能的种类比较少的情况下是比较好的
但在实际应用中这种情况比较少，如果一共有10个数，但每个数可能是1-1000之间的任意整数，这样还不如冒泡来得快
还有
"已知n个互不相同的正整数Si,1<=i<=n,1<=Si<=n"
这个条件似乎已经限制了S这个数组里包含了1到n的所有整数
而最终排序的结果不用算也知道是{1,2,3,...,n}，呵呵
可以啊!