有1,2,……一直到n的无序数组，求排序算法，并且要求……

Question

有1,2,……一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂度为O(1),使用交换，而且一次只能交换两个数。

哪位高手帮我解答一下这道题!谢谢了!
皇家救星1985 - 江湖少侠 请你说明一下你对时间和空间复杂度的计算好不好?谢谢!

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <conio.h>
#include <string.h>
int mysort(int n, int a[])
{
//这个函数就是你问题的答案
//参数n代表数组元素个数,a数组是1,2,……一直到n的无序数组
int temp;
for(int i = 0; i < n; i++)
{
temp = a[a[i] - 1];//将a[i] - 1上的数字保存到temp
a[a[i] - 1] = a[i];//将i上的数字调到正确位置a[i] - 1
a[i] = temp;//并将原来a[i] - 1位置上的数字移到i上
}
return 0;
}

int main()
{//main函数是为了测试用的，只是证明上面函数的正确，与问题无关
int array[100];
int N = 10;
printf("原始数组\n");
for(int i = 0; i < N; i++)
{
array[i] = N - i;
printf("%2d ", array[i]);
}//初始化一个测试数组
printf("\n");

mysort(N, array);
//将数组排序

printf("\n排序后的数组\n");
for(i = 0; i < N; i++)
{
printf("%2d ", array[i]);
}//输出数组
printf("\n\n");
}

Answer 2

#include <stdio.h>
#define N 100
main()
{
int i,j,temp,n;
int a[N];
printf("please enter yao sort number:\n");
scanf("%d",&n);
for(i = 0;i < n;i++)
{
scanf("%d",&a[i]);
}

printf("未排序的数组是:\n");
for(i = 0;i < n;i++)
{
printf("%5d",a[i]);
}
for(i = 0;i < n-1;i++)
{
for(j = i+1;j <n;j++)
{
if(a[i] < a[j])
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
printf("\n排序后的数组是:\n");
for(i = 0; i < n;i++){
printf("%5d",a[i]);
}
printf("\n");
}

Answer 3

说说算法，数组a[n]
for(i=0;i<n;i++)
if(a[i]!=i+1)
swap(a[i],a[a[i]-1]);//把a[0]交换到与索引相应的位置
比如2，1，3
a[0]=2就把a[0]与a[1]交换，变成1，2，3

Answer 4

1楼“黄振_kjxy”还专家呢！傻子都看得出来你的算法是冒泡排序，时间复杂度为O(n^2). 空间复杂度为O(1)的我也没想出来。如果不是O(1)的话，基数排序能达到O(n)的时间复杂度。

Answer 5

上网上去找一下插入排序算法吧...
还有很多算法...选择排序啊...等等..

不过上面那个人给的算法实在是太垃圾了...咋把冒泡给整出来了.