题目：有1,2,3,..n 的无序整数数组，求排序算法。要求时间复杂度 O(n)， 空间复杂度O(1)。
分析：对于一般数组的排序显然 O(n) 是无法完成的。 既然题目这样要求，肯定原先的数组有一定的规律，让人们去寻找一种机会。
例如：原始数组： a = [ 10, 6,9, 5,2, 8,4,7,1,3 ] ，如果把它们从小到大排序且应该是 b = [1,2,3,4,5,6,7,8,9,10 ]，也就是说： 如果我们观察 a --> b 的对映关系是： a[i] 在 b 中的位置是 a[i] - 1，即a[i]=b[a[i]-1]
代码：
#include<iostream>
#include<ctime>
using namespace std;
void print(int* a, int n){
for (int i = ; i < n; i++){
cout << a[i] << ",";
}
cout << endl;
}
void FancySort(int* a, int n){
int temp;
int swapCount = ;
for (int i = ; i < n;)
{
swapCount++;
//a[i]-1为a[i]在有序数组中的位置
//因此a[i]与a[a[i]-1]交换后，a[i]就处于正确位置了
//但交换后的a[a[i]-1]不一定处于正确位置
temp = a[a[i] - ];
a[a[i] - ] = a[i];
a[i] = temp;
cout << "第" << swapCount << "次交换 " << "i=" << i << endl;
print(a, n);
//直到第i位也有了正确的数字，开始处理下一位
if (a[i] == i + )
i++;
}
}
int main(){
while (true){
cout << "输入n：" << endl;
int n;
cin >> n;
int* a = new int[n];
for (int i = ; i < n; i++){
a[i] = ;
}
//对数组（1,2,....一直到n的无序数组）赋予初始化随机值
srand(time());
for (int i = ; i <= n;){
int randV = rand() % n;
if (a[randV] == ){
a[randV] = i;
i++;
}
}
cout << "the input array:";
print(a, n);
FancySort(a, n);
cout << "排序结果:";
print(a, n);
cout << endl;
}
return ;
}
结果：
