有1,2,.....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度为O(1),使用交换,而且一次只能交换两个数。
#include <iostream>
int main()
{
int a[]={10,6,9,5,2,8,4,7,1,3};
int len=sizeof(a)/sizeof(int);
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++;
}
for(int j=0; j<len; j++)
cout << a[j] << ",";
return 0;
}
}
#include <iostream>
int main()
{
int a[]={10,6,9,5,2,8,4,7,1,3};
int len=sizeof(a)/sizeof(int);
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++;
}
for(int j=0; j<len; j++)
cout << a[j] << ",";
return 0;
}
}