首页 > 代码库 > 有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的无序数组，排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。