首页 > 代码库 > 有1,2,3一直到n的无序数组,排序

有1,2,3一直到n的无序数组,排序

题目:有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 = 0; i < n; i++){        cout << a[i] << ",";    }    cout << endl;}
void FancySort(int* a, int n){ int temp; int swapCount = 0; for (int i = 0; i < n;) { swapCount++; //a[i]-1为a[i]在有序数组中的位置 //因此a[i]与a[a[i]-1]交换后,a[i]就处于正确位置了 //但交换后的a[a[i]-1]不一定处于正确位置 temp = a[a[i] - 1]; a[a[i] - 1] = a[i]; a[i] = temp; cout << "" << swapCount << "次交换 " << "i=" << i << endl; print(a, n); //直到第i位也有了正确的数字,开始处理下一位 if (a[i] == i + 1) i++; }}int main(){ while (true){ cout << "输入n:" << endl; int n; cin >> n; int* a = new int[n]; for (int i = 0; i < n; i++){ a[i] = 0; } //对数组(1,2,....一直到n的无序数组)赋予初始化随机值 srand(time(0)); for (int i = 1; i <= n;){ int randV = rand() % n; if (a[randV] == 0){ a[randV] = i; i++; } } cout << "the input array:"; print(a, n); FancySort(a, n); cout << "排序结果:"; print(a, n); cout << endl; } return 0;}

结果:

技术分享

 

有1,2,3一直到n的无序数组,排序