设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数。 试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。
初步思考：最简单的方法就是循环(n-k-1)次，将a数组的末尾数字插入到a[0]之前。
具体做法： (1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。 (2) temp <- a[n-1] (3) 将a[0: n-2] 每个数据都依次向后移动一位赋值给a[1: n-1]。 (4) a[0] <- temp (5) 循环执行(2) -(4) 步 (n-k+1)次。
代价分析： 时间代价—— O((n-1)*(n-k+1)) 即O(n^2)数量级；空间代价： O（1）
我们仔细想想还有没有更快的办法呢？试想一下，如果a[0 : k] 与 a[k+1 : n-1] 正好长度相等，则可以直接一一对应交换即可。 当然，这道题的难点就在于k并不一定是a数组的中间位置。即便如此，但是仍然可以交换：
采用分治算法
当v[k]左边子数组的长度等于右边的子数组长度时，直接将两个子数组对应的元素互换即可 当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数 当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数
通过分析，可知只需要利用保存元素对换时的交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超过O(n)
代码如下：
//交换数组的两段大小相等的范围的对应数据 //a[low1] <->a[low2] a[low1+1]<->a[low2+1] ... a[high1] <-> a[high2] void swap(int a[],int low1,int high1,int low2,int high2){ int temp; while(low1<=high1){ temp=a[low1]; a[low1]=a[low2]; a[low2]=temp; low1++; low2++; } } //利用分治算法， 每次选择最小的数组进行换位 void patition(int a[], int low, int k, int high){ if(low<high){ if((k-low+1)==(high-k)) swap(a,low,k,k+1,high); else if((k-low+1)<(high-k)){ swap(a,low,k,low+high-k,high); patition(a,low,k,low+high-k-1); } else{ swap(a,low,high+low-k-1,k+1,high); patition(a,high+low-k,k,high); } } }以下以数组1，2，| 3，4，5，6，7数组中交换1、2和3、4、5、6、7两个数组块为例分析程序运行过程：
初始数组：1，2，| 3，4，5，6，7 此时： low=0 k=1 high=6 执行： patition(a,0,1,6);
左边长度小于右边 执行： swap(a,0,1,5,6), 将1、2和6、7互换 数组变为： 6，7，3，4，5，1、2 此时： low=0 k=1 high=high-(k-low+1)=4 执行： patition(a,0,1,4);
左边长度小于右边 执行： swap(a,0,1,3,4), 将6、7和4、5互换 数组变为： 4，5，3，6，7，1、2 此时： low=0 k=1 high=high-(k-low+1)=2 执行： patition(a,0,1,2);
左边长度大于右边 执行： swap(a,0,0,2,2), 将4和3互换 数组变为： 3，5，4，6，7，1、2 此时： low=1 k=1 high==2 执行： patition(a,1,1,2);
左边长度等于右边 执行： 将4和5互换 数组变为： 3，4，5，6，7，1、2 结束
当然，此处还有另外一种算法：三次反转算法，类似线性代数中的转置的性质，有如下算法：
算法复杂性分析：3次反转算法最多用了n次数组单元交换运算，每次交换运算需要3次元素移动。因此最坏情况下用了3n次元素移动，时间复杂性为O（n),空间复杂性为 O（1）。
