女装警察:华为的一道排序题帮着看看
来源:百度文库 编辑:高校问答 时间:2024/10/03 16:08:33
原题大意是这样的:
有N个大小不等的自然数(1--N),请将它们由小到大排序。
要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。
网上给的答案是这样
void sort(int e[], int n)
{
int i;
int t; /*临时变量:空间复杂度O(1)*/
for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
{
t = e[e[i]]; /*下标为e[i]的元素,排序后其值就是e[i]*/
e[e[i]] = e[i];
e[i] = t;
}
}
void main()
{
#define MAX 10
int i, a[MAX+1];
printf("Input the number from 1 to %d:\n",MAX);
for (i=1; i<MAX+1; i++)
{
scanf("%d",&a[i]);
}
sort(a,MAX);
printf("\n====sort over====\n");
for (i=1; i<MAX+1; i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
}
我觉得不对,请给出正确的程序
有N个大小不等的自然数(1--N),请将它们由小到大排序。
要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。
网上给的答案是这样
void sort(int e[], int n)
{
int i;
int t; /*临时变量:空间复杂度O(1)*/
for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
{
t = e[e[i]]; /*下标为e[i]的元素,排序后其值就是e[i]*/
e[e[i]] = e[i];
e[i] = t;
}
}
void main()
{
#define MAX 10
int i, a[MAX+1];
printf("Input the number from 1 to %d:\n",MAX);
for (i=1; i<MAX+1; i++)
{
scanf("%d",&a[i]);
}
sort(a,MAX);
printf("\n====sort over====\n");
for (i=1; i<MAX+1; i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
}
我觉得不对,请给出正确的程序
没问题了。
N个大小不等的自然数(1--N)
没有空缺呀.
把值插入相应的位置就好了.
恩,好题!
N个大小不等的自然数(1--N)
这个还要排序么!!!
不就是 1,2,3,4,5,6,.....,N
直接for(int i=1;i<N+1;i++) e[i]=i;
哈哈。