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

可以这样分析,从算法中看,每次交换操作的结果就是把a[i]放到数组中第a[i]个位置,就下标来说是index=a[i]-1,这也是排序结束后a[i]所应该在的位置。那么如果a[i]
已经等于在第a[i]个位置了,那么交换操作其实就是自己跟自己交换了一下,然后if语句成立,i自增1.可以发现,对于任何一个初始元素a[i],它只要通过一次交换操作就
可以到达排序结束后它所应该在的位置,而且以后不会再变动位置。因此,for 循环中所进行的exchange操作一共不超过2*len个,于是算法复杂度是linear!

#include<iostream.h>
 
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;
}

A little bit change in order to save the swap operations if it's already ordered. So the total swap operation will be (n-1) times at most, instead of
2*(n-1) times. In either way, it's O(n).

#include <stdio.h>
 
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
int i=0;
int j;
 
while(i<len)
{
// check if it's ordered or not
if ( a[i] == i + 1) {
i++;
continue;
}
 
// swap
temp = a[a[i] - 1];
a[a[i] - 1] = a[i];
a[i] = temp;
}
 
for (j = 0; j < len; j++)
printf("%d ",a[j]);
printf("\n");
 
return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License