分治法
我們首先先介紹分治法。分治法的思想：將原問題分解為幾個(gè)規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后在合并這些子問題的解來解決原問題的解。
還是拿撲克牌舉例子，假設(shè)桌上有兩堆牌面朝上的牌(牌面朝上：有值)，每堆都已排序，最小的牌在頂上。我們希望把這兩堆牌合并成單一的排好序的輸出堆，牌面朝下地放在桌上。應(yīng)該怎么做呢？
我們的做法是：在牌面朝上的兩堆牌的頂上兩張牌中選取較小的一張，將該牌從其堆中移開(該堆的頂上將顯示一張新牌)并牌面朝下地將該牌放置到輸出堆。重復(fù)這個(gè)步驟直到兩堆牌都沒有牌。
下面我們來實(shí)現(xiàn)上面所提的思想
為了避免在某個(gè)基本步驟必須檢查是否有堆為空。在每個(gè)堆的底部放置一張哨兵牌，它包含一個(gè)特殊的值(很大的值，使它不可能是較小的牌，除非兩個(gè)堆都已顯露出其哨兵牌。一旦發(fā)生這種情況，說明非哨兵牌都已被放置到輸出堆)，用于簡化代碼。
偽代碼：
MERGE(A,p,q,r)n1 = q - p + 1n2 = r - q//L[1..n1+1] and R[1..n2+1]是新的數(shù)組for i = 1 to n1L[i] = A[p + i -1]for j = 1 to n2R[j] = A[q + j]L[n1 + 1] = ∞R[n2 + 1] = ∞i = 1j = 1for k = p to rif L[i] <= R[j]A[k] = L[i]i = i + 1elseA[k] = R[j]j = j + 1
Java實(shí)現(xiàn)：
public void Merge(int[] A,int p,int q,int r){int n1 = q - p + 1;int n2 = r - q;//L[1..n1+1] and R[1..n2+1]是新的數(shù)組int[] L = new int[n1 + 1];int[] R = new int[n2 + 1];for (int i = 0;i < n1;i++){L[i] = A[p + i];}for (int j = 0;j < n2;j++){R[j] = A[q + j + 1];}L[n1] = Integer.MAX_VALUE;R[n2] = Integer.MAX_VALUE;int i = 0,j = 0;for (int k = p;k <= r;k++){if (L[i] <= R[j]){A[k] = L[i];i = i + 1;}else{A[k] = R[j];j = j + 1;}}}下面我們來看一下分治法的步驟
對(duì)數(shù)組A[2,4,7,1,3,6]調(diào)用Merge(A,0,2,5)
初始狀態(tài)
初始完L和R數(shù)組之后，現(xiàn)在進(jìn)入for循環(huán)階段。讓L中i所指的值和R數(shù)組中j所指的值進(jìn)行比較，把較小的值放入數(shù)組A中k所指的位置。并且讓較小的值的索引i或j前進(jìn)一格(+1)。因?yàn)長和R數(shù)組已經(jīng)從小到大排好序了，所以找出來的最小值一定是當(dāng)前L和R數(shù)組的最小值，放入了數(shù)組A中也是排好序的，所以讓k前進(jìn)一步，k=k+1,然后執(zhí)行下一次循環(huán)。
第一此循環(huán)：i和j初始為0，k=p=0，讓L[0]與R[0]進(jìn)行比較 L[0]>R[0]所以R[0]是較小值，把A[0]替換為R[0]。讓j=j+1，i保持不變。k=k+1=1，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
A中的灰色位置包含將被覆蓋的值，L和R中的灰色位置包含有待于被復(fù)制回A的值，A中的黃色位置包含它們的最終值，L和R中的黃色位置包含已被復(fù)制回A的值。
第二次循環(huán)：此時(shí)i=0，j=1，k=1，讓L[i]和R[j]進(jìn)行比較，L[0]<R[1]，所以L[0]是較小值，把A[k]即A[1]替換為L[0]。讓i=i+1，j保存不變。k=k+1=2，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
第三次循環(huán)：此時(shí)i=1，j=1，k=2，讓L[i]和R[j]進(jìn)行比較，L[1]>R[1]，所以R[1]是較小值，把A[2]即A[2]替換為R[1]。讓j=j+1，i保存不變。k=k+1=3，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
第四次循環(huán)：此時(shí)i=1，j=2，k=3，讓L[i]和R[j]進(jìn)行比較，L[1]<R[2]，所以L[1]是較小值，把A[k]即A[3]替換為L[1]。讓i=i+1，j保存不變。k=k+1=4，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
第五次循環(huán)：此時(shí)i=2，j=2，k=4，讓L[i]和R[j]進(jìn)行比較，L[2]>R[2]，所以R[2]是較小值，把A[k]即A[4]替換為R[2]。讓j=j+1，j保存不變。k=k+1=4，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
注意：此時(shí)j已經(jīng)到達(dá)了R數(shù)組的最后一個(gè)數(shù)∞，L數(shù)組中的每個(gè)數(shù)都比∞小，即不等式L[i]>R[j]恒成立。所以不管L剩下多少個(gè)數(shù)，都會(huì)按照順序放置A中，直到i也達(dá)到了最后一個(gè)數(shù)∞，此時(shí)k>r，循環(huán)已經(jīng)全部結(jié)束。
第六次循環(huán)：此時(shí)i=2，j=3，k=5，讓L[i]和R[j]進(jìn)行比較，L[2]<R[3]，所以L[2]是較小值，把A[k]即A[5]替換為L[2]。讓i=i+1，j保存不變。k=k+1=6，開啟下一次循環(huán)。本次循環(huán)結(jié)果如下圖所示：
第七次循環(huán)，此時(shí)i=2，j=3，k=6，我們的r=5，判斷條件k<=r為false，循環(huán)結(jié)束。
分治法的應(yīng)用——?dú)w并排序
上面講到了分治法，分治法有個(gè)很大的限制就是L和R是排好序的才可以。但是許多數(shù)組都是很亂的順序。那么怎么解決這個(gè)問題呢？試想一下如果L和R數(shù)組的大小為1，那么L和R數(shù)組肯定是排好序的。對(duì)的！我們可以把一個(gè)大的數(shù)組遞歸拆分成小的子數(shù)組，子數(shù)組在遞歸拆分成更小的子數(shù)組。直到遞歸到的L和R數(shù)組的大小為1時(shí)，調(diào)用MERGE分治法。隨著算法自底向上地推進(jìn)：合并只含1項(xiàng)的序列對(duì)形成長度為2的排好序的序列，合并長度為2的序列對(duì)形成長度為4的排好序的序列，依次下去，直到長度為n/2的兩個(gè)序列被合并最終形成長度為n的排好序的序列，數(shù)組最終會(huì)排序完成。
如下圖所示
我們可以把上面提到的MERGE作為歸并排序算法中的一個(gè)子程序來用。
下面的過程MERGE-SORT(A,p,r)排序子數(shù)組A[p…r]中的元素。若p>=r,則該子數(shù)組最多有一個(gè)元素，所以已經(jīng)排好序。否則，分解步驟簡單地計(jì)算一個(gè)下標(biāo)q，將A[p…r]分成兩個(gè)子數(shù)組A[p…q]和A[q+1…r]，前者包含n/2個(gè)元素，后者包含n/2個(gè)元素。
偽代碼：
MERGE-SORT(A,p,r)if p < rq = (p+r)/2MERGE-SORT(A,p,q)MERGE-SORT(A,q+1,r)MERGE(A,p,q,r)
java實(shí)現(xiàn)：
public void MergeSort(int[] A,int p,int r) {if (p < r){int q =(int)Math.floor((p+r)/2);MergeSort(A,p,q); //將左半邊排序MergeSort(A,q+1,r); //將右半邊排序Merge(A,p,q,r); //歸并結(jié)果}}
下面我們來看一下歸并排序在數(shù)組A=[5,2,4,7,1,3,2,6]上的操作，隨著算法自底向上地推進(jìn)，待合并的已排好序的各序列的長度不斷增加。
合肥北大青鳥一元校區(qū)是隸屬于北大青鳥旗下的一家IT培訓(xùn)機(jī)構(gòu)，這里有豐富的Java教育資源，完善的教育體系，和多個(gè)大型企業(yè)擁有合作，學(xué)員學(xué)完課程之后推薦就業(yè)【北大青鳥一元校區(qū) www.kgcbdqn.com】百度搜索“北大青鳥一元校區(qū)”,即可領(lǐng)取試聽課程
