1
/**////////////////////////////////////////////////// 2
//迅雷筆試題：
3//有N個(gè)大小不等的自然數(shù)（1--N），請(qǐng)將它們由小到大排序。
4//要求程序算法：時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。
5
6#define TEST_XUNLEI
7
8#ifdef TEST_XUNLEI
9
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 //保證空間復(fù)雜度為O(1)
26 int tmp = 0;
27 for(int i = 0;i < n;i++)
28 {
29 //移動(dòng)，直到第data[i]為i+1的時(shí),while結(jié)束循環(huán)。向后繼續(xù)判斷
30 while(data[i] != i+1)
31 {
32 //每次循環(huán)保證了data[i-1]的正確。總共有n個(gè)所以時(shí)間復(fù)雜度為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}
43
44
45#endif
該題的重點(diǎn)在于，N個(gè)1--N的數(shù)。