使用最少的空间调整元素的位置
数组(n是奇数)
A0 A1 A2 A3 A4 A5 A6 A7...An
=>
A0 A2 A4 A6...A1 A3 A5 A7...An
有没有简单的算法？
[解决办法]
o(1)的空间，O(n^2)的时间行不？
[解决办法]
一般的算法大多会导致多用一个临时空间,不用空间交换的算法大概只有一个了,位运算.自己写个函数,完成两个数数值的交换就可以了
[解决办法]
又见到这个问题，有个n*log(n),O(1)的分治方法，O(n),O(1)的方法还没想到
[解决办法]
快速排序，O(nlgn)的时间复杂度，O(1)的空间。
[解决办法]
这道题有O(n)的方法。不过“可能”需要O(n)的辅助空间。
因为只按照数组下标的规律，所以我们可以找到一个通用公式
Ai在新数组的位置是 (i&1) * (n/2+1) + i/2
next(i) = (i&1) * (n/2+1) + i/2
for p从0开始向后扫描至数组末尾，遇到处理过的元素跳过
{
q = p
tmp = Aq;
标记Aq为处理过。
do { swap( Anext(q), tmp ); 标记Anext(q)为处理过; q = next(q); } while( q != p );
}
标记处理需要额外的O(n)空间，但是，如果原来的元素都是正整数，那么可以将处理过的元素标记为相反数，等到最后都处理完了，再把所有数据改回正整数。
