最近剛學(xué)習(xí)算法設(shè)計與分析的課程，所用教材是清華大學(xué)出版社王曉東編著的《算法設(shè)計與分析》。一道關(guān)于遞歸與分治算法的練習(xí)題如下：
剛拿到題目覺得這題目似乎和遞歸分治沒有什么關(guān)系，但是O(1)的空間復(fù)雜度，以及O(n)的時間復(fù)雜度度就限制了解決方法，也就是分治和遞歸。(使用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))
現(xiàn)在我們來思考這個遞歸分治算法。
開始前先說明一下變量含義：
start:左邊子數(shù)組開始位置下標(biāo)
sep:分割位置下標(biāo)(左邊子數(shù)組結(jié)束位置下標(biāo))
end:右邊子數(shù)組結(jié)束位置下標(biāo)
首先，是最簡單的情況，相信大家一定能想到，如果兩個子數(shù)組長度相等，直接遍歷子數(shù)組的長度，寫上三行交換代碼就可以解決了。(在這就不給出圖例了，簡單腦補一下即可)
接下來，就是剩余兩種情況：分別是左邊子數(shù)組長度>右邊子數(shù)組長度以及左邊子數(shù)組長度<右邊子數(shù)組長度。我的基本想法就是長度小的一邊可以直接交換到位，長度長的一邊分成兩部分，一部分就是長度短的子數(shù)組長度，另一部分就是剩余部分長度。即：
長數(shù)組用和短數(shù)組相同長度的元素和短數(shù)組元素一一交換，長數(shù)組剩余元素不動。第一次交換完成后短數(shù)組已經(jīng)直接到位，接下來處理剩余元素長度即可，從而問題規(guī)?？s小，使用分治遞歸可以解決。
下面圖例都是以這個數(shù)組為例{1，2，3，4，5，6，7}(紅色字體表示已經(jīng)到位的元素)
圖一(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直接交換位置，所有元素全部到位。
接下來是代碼呈現(xiàn)：
public static void exchange(int a[],int start,int sep,int end)
{ 鄭州婦科醫(yī)院 http://www.zyfuke.com/
int t;
// 左邊子數(shù)組長度 = 右邊子數(shù)組長度
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;
}
}
// 左邊子數(shù)組長度 > 右邊子數(shù)組長度
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);
//遞歸調(diào)用exchange方法
// exchange(a, start, sep, end);
}
// 左邊子數(shù)組長度 < 右邊子數(shù)組長度
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);
//遞歸調(diào)用exchange方法
exchange(a, start, sep, end);
}
}
左邊子數(shù)組長度 >右邊子數(shù)組長度：
左右兩邊交換，中間不動，交換后左邊部分完成，右邊遞歸，*start前進短的子數(shù)組的長度個單位，*短的子數(shù)組長度=end-sep，所以有start=start+end-sep;sep不變,end也不變。
左邊子數(shù)組長度 <右邊子數(shù)組長度：
左邊中間交換，右邊不動，交換后左邊部分完成，右邊遞歸，start前進短的子數(shù)組的長度個單位，短的子數(shù)組長度=sep-start+1，所以有start=start+sep-start+1=sep+1。sep也前進短子數(shù)組長度個單位，sep=sep+sep-start+1;end不變。
測試：
int a[]= {10,2,8,3,5,4,7,1};
...
exchange(a, 0,4,a.length-1);
重慶分公司
重慶分公司
