[半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
