有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数
有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数
这个的代码如何写？？？？
[解决办法]
这个条件比较特殊，所以可以实现O(n)的算法，也可以不交换2个数。如果a[j]!=j，则把a[j]中的元素放到它应在的位置，同时把要被覆盖的元素取出来。不停循环，一直到a[j] = j;
简单写一下代码：
for (i=1; i<=n; i++)
{
j = i;
while (a[j] != j)
{
cache = a[a[j]];
a[a[j]] = a[j];
j = cache;
}
}
虽然for 中嵌套了一个while，但最多循环2次。
[解决办法]
