我给一个交换策略，但是算法复杂度为O(n^2)
思路是：
第一步，交换,n和n+1位置上的元素，也就是an和b1,序列变为a1,a2,...,b1,an,b2,...,bn
第二步，交换,n-1和n, n+1和n+2,序列变为a1,a2,...,an-1,b1,b2,an,...,bn
...
第i步，交换，(n-i,n-i+1), (n-i+2, n-i+3),...,(n+i-1, n+i)位置。
程序如下：
代码:
#include <cstdlib>
#include <iostream>
using namespace std;
void trans(int* x, int n){
for(int i=1; i<n; ++i)
for(int j=0; j<i; ++j)
std::swap(x[n-i+2*j],x[n-i+2*j+1]);
}
void print_list(int* x, int n){
for(int i=0; i<n; ++i)
std::cout<<x[i]<<",";
std::cout<<"\n";
}
int main(int argc, char *argv[])
{
int a[]={1,3,5,7,9,2,4,6,8,10};
print_list(a, sizeof(a)/sizeof(int));
trans(a, sizeof(a)/sizeof(int)/2);
print_list(a, sizeof(a)/sizeof(int));
}
测试如下
chen@chen-PC /cygdrive/d/liuxinyu/temp/c++
$ g++ main.cpp
chen@chen-PC /cygdrive/d/liuxinyu/temp/c++
$ ./a
1,3,5,7,9,2,4,6,8,10,
1,2,3,4,5,6,7,8,9,10,
这里显然有冗余交换。所以时间复杂度才没有达到O(n)，但是交换策略非常一致。