递归与分治算法练习

　　最近刚学习算法设计与分析的课程，所用教材是清华大学出版社王晓东编著的《算法设计与分析》。一道关于递归与分治算法的练习题如下：

　　刚拿到题目觉得这题目似乎和递归分治没有什么关系，但是O(1)的空间复杂度，以及O(n)的时间复杂度度就限制了解决方法，也就是分治和递归。(使用python语言只需几行，用切片即可完成，这里附上极其弱智的代码)

　　def exchange(a,k):

　　a=a[k:]+a[0:k]#列表切片

　　return a

　　ls=[1,2,3,4,5,6,7]

　　print(exchange(ls,4))

　　现在我们来思考这个递归分治算法。

　　开始前先说明一下变量含义：

　　start:左边子数组开始位置下标

　　sep:分割位置下标(左边子数组结束位置下标)

　　end:右边子数组结束位置下标

　　首先，是最简单的情况，相信大家一定能想到，如果两个子数组长度相等，直接遍历子数组的长度，写上三行交换代码就可以解决了。(在这就不给出图例了，简单脑补一下即可)

　　接下来，就是剩余两种情况：分别是左边子数组长度>右边子数组长度以及左边子数组长度<右边子数组长度。我的基本想法就是长度小的一边可以直接交换到位，长度长的一边分成两部分，一部分就是长度短的子数组长度，另一部分就是剩余部分长度。即：

　　长数组用和短数组相同长度的元素和短数组元素一一交换，长数组剩余元素不动。第一次交换完成后短数组已经直接到位，接下来处理剩余元素长度即可，从而问题规模缩小，使用分治递归可以解决。

　　下面图例都是以这个数组为例{1，2，3，4，5，6，7}(红色字体表示已经到位的元素)

　　图一(start=0,sep=4,end=6)：

　　判断是左边大于右边;长度为2的两对交换。1，2和6，7互换位置;6，7到位。start前进2位(start=2)，sep不变，end也不变。

　　判断是左边大于右边;1，2和6，7互换位置;6，7，1，2到位。start再前进2位(start=4)，sep不变，end也不变。

　　判断是左边小于右边;5和3互换位置;6，7，1，2，3到位。start前进1位(start=5),sep增1(sep=5),end不变。

　　判断是左边等于右边;5和4直接交换位置，所有元素全部到位。

　　图二(start=0,sep=1,end=6)：

　　判断是左边小于右边;长度为2的两对交换。1，2和3，4互换位置;3，4到位。start前进2位(start=2)，sep前进1位(sep=3)，end也不变。

　　判断是左边小于右边;1，2和5，6互换位置;3，4，5，6到位。start再前进2位(start=4)，sep前进2位(sep=5)，end也不变。

　　判断是左边大于右边;5和3互换位置;6，7，1，2，3到位。start前进1位(start=5),sep增1(sep=5),end不变。

　　判断是左边等于右边;2和1直接交换位置，所有元素全部到位。

　　接下来是代码呈现：

　　public static void exchange(int a[],int start,int sep,int end)

　　{郑州妇科医院 Http://www.zyfuke.com/

　　int t;

　　// 左边子数组长度 = 右边子数组长度

　　if(end-sep==sep-start+1)

　　{

　　for (int i = start; i <=sep; i++)

　　{

　　t=a[i];

　　a[i]=a[i+sep-start+1];

　　a[i+sep-start+1]=t;

　　}

　　}

　　// 左边子数组长度 > 右边子数组长度

　　if(end-sep

　　{

　　for(int i=end;i>=sep+1;i--)

　　{

　　t=a[i];

　　a[i]=a[i-(sep-start+1)];

　　a[i-(sep-start+1)]=t;

　　}

　　// start=start+end-sep;

　　exchange(a, start+end-sep, sep, end);

　　//递归调用exchange方法

　　// exchange(a, start, sep, end);

　　}

　　// 左边子数组长度 < 右边子数组长度

　　if(end-sep>sep-start+1)

　　{

　　for(int i=start;i<=sep;i++)

　　{

　　t=a[i];

　　a[i]=a[i+sep-start+1];

　　a[i+sep-start+1]=t;

　　}

　　// start=sep+1;

　　// sep=sep+sep-start+1;

　　exchange(a, sep+1, sep+sep-start+1, end);

　　//递归调用exchange方法

　　exchange(a, start, sep, end);

　　}

　　}

　　左边子数组长度 >右边子数组长度：

　　左右两边交换，中间不动，交换后左边部分完成，右边递归，*start前进短的子数组的长度个单位，*短的子数组长度=end-sep，所以有start=start+end-sep;sep不变,end也不变。

　　左边子数组长度 <右边子数组长度：

　　左边中间交换，右边不动，交换后左边部分完成，右边递归，start前进短的子数组的长度个单位，短的子数组长度=sep-start+1，所以有start=start+sep-start+1=sep+1。sep也前进短子数组长度个单位，sep=sep+sep-start+1;end不变。

　　测试：

　　int a[]= {10,2,8,3,5,4,7,1};

　　...

　　exchange(a, 0,4,a.length-1);