菜鸟请教一道1到N自然数排序的华为面试题

Question

有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; 
} 
} 
可我用它对数组5,4,3,1,2排序，怎么不行呢？ 
是那个算法的问题么？ 
如果那个算法不对，那正确的应该是什么样的？ 
这里高人众多，希望有人帮助
对，忘了，关于数组下标开始是0的问题，我已经考虑到了。可按那个算法排完了应该是2，1，3，4，5啊

Answer 1

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;
  }
 }
} 

Answer 2

void   sort{for(i=0;i<n;i++)
{
if(a[i]>a[i+1]){
 int temp;
 temp=a[i];
 a[i]=a[i+1];
 a[i+1]=temp;
 }
else 
     continue;}
}

Answer 3

似乎结帖早了点
我还有问题请问1楼，你给出的方法，for循环里还有个while循环，时间复杂度还是O(n)么？为什么？

Answer 4

int[] arr;
int t;
for(int i=0;i<arr.length;i++){
while(arr[i]-1!=i){
t=arr[arr[i]-1];
arr[arr[i]-1]=arr[i];
arr[i]=t;
}
选择排序,while中的程序最坏情况下执行N次.时间复杂度为O(N).(时间复杂度不必计算while语句本身).
可以参考下面连接内容:
http://www.mldn.cn/articleview/2007-9-13/article_view_2381.htm