from : http://blog.csdn.net/livelylittlefish/article/details/2104007
对“google面试题及我的算法（1）——改进”的再改进
不需要移动，通过交换完成，只需一个交换空间
例如，N=9时，第2步执行后，实际上中间位置的两边对称的4个元素基本配对，只需交换中间的两个元素即可，如下表所示。颜色表示每次要交换的元素,左边向右交换,右边向左交换。交换过程如下表所示。
交换x1,x3；交换x2,x4；再交换中间的x1,x4；交换y1,y2；
算法思想：
以N=9为例(中间的竖表示中间位置):
a1 a2 a3 a4 a5 a6 a7 a8 a9 | b1 b2 b3 b4 b5 b6 b7 b8 b9
头尾的元素不需任何操作
1. 左边从位置left=2开始，右边从位置n+1开始，向右交换count=1个元素，即a2,b1交换
右边从位置right=2n-1开始，左边从位置n开始，向左交换count=1个元素，即b8,a9交换
序列变为：
a1 b1 a3 a4 a5 a6 a7 a8 b8 | a2 b2 b3 b4 b5 b6 b7 a9 b9
故已经成功放好位置的有(a1,b1),(a9,b9)
其中(a8,b8),(a2,b2)也配对，只需将其交换到相应的位置即可
2. 左边从位置left=3开始，右边从位置n+1开始，向右交换count=2个元素，即a3 a4 和 a2 b2交换
右边从位置right=2n-2开始，左边从位置n开始，向左交换count=2个元素，即b6 b7 和 a8 b8交换
序列变为：
a1 b1 a2 b2 a5 a6 a7 b6 b7 | a3 a4 b3 b4 b5 a8 b8 a9 b9
故又成功放好位置的有(a2,b2),(a8,b9)
3. 左边从位置left=5开始，右边从位置n开始，已不能满足交换count=4个元素的要求，故退出循环
4. 序列缩小为a5 a6 a7 b6 b7 | a3 a4 b3 b4 b5, 对序列中没有放好的数据按快处理
将序列看作：x1=(a5) y1=(a6 a7 b6) x2=(b7) | x3=(a3) y2=(a4 b3 b4) x4=(b5)
交换x1,x3；交换x2,x4；再交换中间的x1,x4；交换y1,y2；
此时序列变为S1：a3 a4 b3 b4 a5 b5 a6 a7 b6 b7
5. 若交换到左边的b有配对的a，则中间的序列S2=(a5 b6)作为新的序列；否则将S1作为新的序列；对该序列进行上述操作，直到所有元素都放到正确的位置
此例中，(a6,a7,b6,b7),(a3,a4,b3,b4)以配对，只需交换中间的两个元素即可，序列缩小a5 b5
=====================================================================
为方便比较，序列变化如下：
a1 a2 a3 a4 a5 a6 a7 a8 a9 | b1 b2 b3 b4 b5 b6 b7 b8 b9
a1 b1 a3 a4 a5 a6 a7 a8 b8 | a2 b2 b3 b4 b5 b6 b7 a9 b9
a1 b1 a2 b2 a5 a6 a7 b6 b7 | a3 a4 b3 b4 b5 a8 b8 a9 b9
a1 b1 a2 b2 a3 a4 b3 b4 a5 | b5 a6 b6 a7 b7 a8 b8 a9 b9
a1 b1 a2 b2 a3 b3 a4 b4 a5 | b5 a6 b6 a7 b7 a8 b8 a9 b9
源代码如下：
/************************************************************************
* 输入a1,a2,...,an,b1,b2,...,bn * 在O(n)的时间,O(1)的空间 * 将这个序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn
************************************************************************/
#include <stdio.h>#include <string.h>#include <CONIO.H>#define MAXSIZE 2*100000int exchangetimes=0; //交换次数//交换两个数据void swap(int *x,int *y){ int t; t=*x; *x=*y; *y=t; exchangetimes++;}//按要求交换序列(假设元素从下标1开始存放)void exchange(int a[],int m){ int n=m/2; if(n==1) //a1,b1 ==>不需交换 return; else if(n==2) //a1,a2,b1,b2 ==>只需交换中间的两个数据
{ swap(a+1,a+2); return;
} int done; //已经处理的数据个数 int left; //左边开始交换的位置 int right; //右边开始交换的位置 int count; //每次交换的数据个数 int lefta; //左边未处理的a个数 int notmatch; //左边未匹配的a个数 //初始化 done=1; left=1; //左边从位置1开始向右交换 right=2*n-2; //右边从位置2*n-2开始向左交换 count=1; //每次交换count个数据 lefta=notmatch=n-1; while(1) { //左边从left开始和右边从n开始向右交换count个数据 for(int j=0;j<count;j++) swap(a+left+j,a+n+j); //右边从right开始和左边从n-1开始向左交换count个数据 for(j=0;j<count;j++) swap(a+right-j,a+n-1-j); //交换后将其调整为要求的序列 if(count>=4) { exchange(a+left,count); exchange(a+right-count+1,count); } //重新调整各变量 done+=count; lefta=n-done-count; notmatch=lefta-count; left=left+count; right=right-count; count*=2; if(notmatch<count) break; } int x,y; //左边剩下的a不能与从右边交换过来的b配对 //如n=13时,上面的循环结束后变为: a9 (b6 b7 b8) b9 | a5 (a6 a7 a8) b5 //此时,lefta=1,notmatch<0,分块交换,各个块如下 //x1=(a9), y1=(b6 b7 b8), x2=(b9), x3=(a5), y2=(a6 a7 a8), x4=(b5) //上述序列变为 x1 y1 x2 x3 y2 x4, x的长度均为1,y的长度均为3 //x1 x3交换,x2 x4交换==>x3 x4 x1 x2,然后中间的x4 x1交换==>x3 x1 x4 x2 //y1 y2交换==>y2 y1 //上述6块经4次交换后变为 x3 y2 x1 x4 y1 x2 //n=13时,经上述交换后变为 a5 a6 a7 a8 a9 b5 b6 b7 b8 b9 if(notmatch<0) { count/=2; //if n=13, then here count=4 x=lefta; //x块的长度,if n=13, then heare x=1 } else { //递归调用中间对称的count个数据 exchange(a+n-count,count); exchange(a+n,count); x=notmatch; } ////////////////////////////////////////////////////////////////////////// y=count-x; //y块的长度,if n=13, then heare y=3 //左边从left开始和右边从n开始向右交换x个数据,即x1 x3交换 //右边从right开始和左边从n-1开始向左交换x个数据,即x2 x4交换 for(int j=0;j<x;j++) { swap(a+left+j,a+n+j); //左边向左交换 swap(a+right-j,a+n-1-j); //右边向左交换 } //交换到中间的x1 x4交换 for(j=0;j<x;j++) swap(a+n-x+j,a+n+j); //交换y1 y2数据块 for(j=0;j<y;j++) swap(a+left+x+j,a+n+x+j); ////////////////////////////////////////////////////////////////////////// //处理余下的序列 if(notmatch<0) { int newm=2*(n-left); //或者size=x+count exchange(a+left,newm); } else if(notmatch>0) { int newm=2*notmatch; exchange(a+left+count,newm); }}//显示菜单void show_menu(){ printf("--------------------------------------------- "); printf("input command to test the program "); printf(" i or I : input n to test "); printf(" t or T : test program "); printf(" q or Q : quit "); printf("--------------------------------------------- "); printf("$ input command >");}//显示数据void display(int a[],int n){ for(int i=0; i<n;i++) printf("%3d",a[i]); printf(" ");}//检查交换是否正确bool check(int a[],int n){ int i; for(i=0;i<n-2;i+=2) { if(a[i]!=i/2+1) return false; } for(i=1;i<n-1;i+=2) { if(a[i]!=(n+i+1)/2) return false; } return true;}void main(){ int a[MAXSIZE]; int n; char sinput[10]; show_menu(); scanf("%s",sinput); while(stricmp(sinput,"q")!=0) { if(stricmp(sinput,"i")==0) { printf(" please input n:"); scanf("%d",&n); //且假设数组中的数据为1,2,3,...,n,n+1,n+2,...,2n for(int i=0; i<2*n;i++) //初始化 a[i]=i+1; display(a,2*n); exchangetimes=0; //交换 exchange(a,2*n); display(a,2*n); printf(" exchange times: %d ",exchangetimes); } else if(stricmp(sinput,"t")==0) { int n1,n2; printf(" please input the begin number:"); scanf("%d",&n1); printf(" please input the end number:"); scanf("%d",&n2); printf(" press any key to start ... "); getch(); for(int i=n1;i<=n2;i++) { //初始化 for(int j=0; j<2*i;j++) a[j]=j+1; exchangetimes=0; exchange(a,2*i); if(check(a,2*i)) printf(" n=%d ... ok! exchange times: %d ",i,exchangetimes); else printf(" n=%d ... wrong! ",i); } printf(" "); } //输入命令 printf("$ input command >"); scanf("%s",sinput); }}为方便讨论，贴出两个运行结果的图片：
1. 输入n
2. 测试从n1~n2的所有n是否能正确运行，并提供其交换次数
