神马品牌网致命自主武器系统:华为的一道排序题帮着看看
来源：百度文库 编辑：神马品牌网 时间：2024/04/28 02:22:36
原题大意是这样的：
有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;
哈哈。