[半zz]迅雷笔试题

1  /////////////////////////////////////////////////
2 //迅雷笔试题:
 3//有N个大小不等的自然数(1–N),请将它们由小到大排序。   
 4//要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。

10#include <iostream>
11using namespace std;
12int sort(int data[],int n);
13int main()
14{
15    int data[] = {8,7,9,4,6,5,3,2,1};
16    for(int i = 0 ;i < sizeof(data)/sizeof(int);i++)
17        cout<<data[i]<< ;
18    cout<<endl;
19    sort(data,sizeof(data)/sizeof(int));
20    system(pause);
21    return 1;
22}

23int sort(int data[],int n)
24{
25    //保证空间复杂度为O(1)
26    int tmp = 0;               
27    for(int i = 0;i < n;i++)    
28    {
29       //移动,直到第data[i]为i+1的时,while结束循环。向后继续判断
30        while(data[i] != i+1)   
31        
32            //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)
33            tmp = data[data[i]1];
34            data[data[i]1= data[i];        
35            data[i] = tmp;
36        }

37    }

38    for(int i = 0;i < n;i++)
39        cout<<data[i]<< ;
40    cout<<endl;
41    return 1;
42}

看了这题,我也花了些时间想了想,结果想出来的代码和这家伙的有些不一样,

我想不能让我白想啊,所以把自己的代码也贴上来,嘿嘿。。。。

    for(int i = 0;i < n;)   
    {
       //移动,直到第data[i]为i+1的时,while结束循环。向后继续判断
//         while(data[i] != i+1)  
//         {
//             //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)
//             tmp = data[data[i]-1];
//             data[data[i]-1] = data[i];       
//             data[i] = tmp;
//         }
  if (data[i] != i+1)
  {
             tmp = data[data[i]-1];
             data[data[i]-1] = data[i];       
             data[i] = tmp;
  }
  else i++;
    }

思想是一样的,我感得还是我的好理解些,起码我只用了一重循环 ;D