学步园

#include <iostream>  
using namespace std;  
/* 
输入a1,a2,...,an,b1,b2,...,bn,  
在O(n)的时间,O(1)的空间将这个序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn， 
且不需要移动，通过交换完成，只需一个交换空间。 
 
一 
a1a2a3a4  b1b2b3b4 
a1a2b1b2  a3a4b3b4 
二 
a1a2a3a4a5 b1b2b3b4b5 
a1a2b1b2b3 a3a4a5b4b5 
a1a2b1b2a3 b3a4a5b4b5 
 
*/    

  void solve(int arr[],int s ,int e)  
    {  
      
        if( s >= e)  
            return;  
      
        int center = (s+e)/2;  
      
        //left part: s,...,center;  
        //right part center+1,...,e  
        int ls = s;  
        int le = center;  
        int rs = center+1;  
        int re = e;   
      
        for(int i=(le+ls)/2+1,j = rs ; i <= le; i++,j++)  
            mySwap(arr[i],arr[j]);  
      
        //奇数个  
        if(le!=ls && (le-ls)%2==0){  
            le++;  
            rs--;  
        }     
      
        solve(arr,ls,le);  
        solve(arr,rs,re);  
      
    }  
	
	  
int main()  
{  
    int arr[]={1,3,5,7,9,2,4,6,8,10};  
  solve(arr,0 ,9);  
  for(int i=0;i<10;i++)  
      cout<<arr[i]<<" ";  
  cout<<endl;  
  return 0;  
}