遞歸與分治算法練習

　　最近剛學習算法設計與分析的課程，所用教材是清華大學出版社王曉東編著的《算法設計與分析》。一道關于遞歸與分治算法的練習題如下：

　　剛拿到題目覺得這題目似乎和遞歸分治沒有什么關系，但是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);