一个被传为华为的面试题
有N个大小不等的自然数（1--N），请将它们由小到大排序。
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
网上转的，一开始也没有注意到最开始的半句。
算法：N个不等的自然数1~N，排序完成后必然为1~N。所以可以一次遍历，遇到a[i]!=i的就把a[i]和a[a[i]]交换。
void sort(int a[], int n)
{
int i;
int t; /*临时变量：空间复杂度O(1)*/
for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
{
while(a[i]!=i)
{
t = a[a[i]];
a[a[i]] = a[i];//排好一个元素
a[i] = t;
}
}
}
这个百度搜到很多这样的。
question 1：这个明明就是很简单的题目 只要一个for 并且使得a[i]=i不就结束了吗？？何必浪费这么多时间，
questions 2：即便用这个方法 那么时间复杂度貌似不只是0（n）吧。是的话请详细说明
[解决办法]
既然N个自然数是1-N，不用排序了，直接a[i]=i,就行了，遍历一遍，复杂度O(N)
[解决办法]
...直接赋值。。。
