学步园

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

#include <iostream.h>
void sort(int *a,int len)
{
	int temp;
	for(int i = 0; i < len; )
	{
		temp = a[a[i] - 1];
		a[a[i] - 1] = a[i];
		a[i] = temp;
		
		if (a[i] == i + 1)
			i++;
	}
}
int main()
{
	int a[] = {10,6,9,5,2,8,4,7,1,3};
	int len = sizeof(a) / sizeof(int);
    sort(a,len);
	for (int j = 0; j < len; j++)
		cout<<a[j]<<" ";
	cout<<endl;
	return 0;
}