分治法
我們首先先介紹分治法。分治法的思想：將原問(wèn)題分解為幾個(gè)規(guī)模較小但類(lèi)似于原問(wèn)題的子問(wèn)題级解，遞歸地求解這些子問(wèn)題冒黑，然后在合并這些子問(wèn)題的解來(lái)解決原問(wèn)題的解。
還是拿撲克牌舉例子勤哗，假設(shè)桌上有兩堆牌面朝上的牌(牌面朝上：有值)抡爹，每堆都已排序，最小的牌在頂上芒划。我們希望把這兩堆牌合并成單一的排好序的輸出堆冬竟，牌面朝下地放在桌上。應(yīng)該怎么做呢民逼？
我們的做法是：在牌面朝上的兩堆牌的頂上兩張牌中選取較小的一張泵殴，將該牌從其堆中移開(kāi)(該堆的頂上將顯示一張新牌)并牌面朝下地將該牌放置到輸出堆。重復(fù)這個(gè)步驟直到兩堆牌都沒(méi)有牌拼苍。
下面我們來(lái)實(shí)現(xiàn)上面所提的思想
為了避免在某個(gè)基本步驟必須檢查是否有堆為空袋狞。在每個(gè)堆的底部放置一張哨兵牌，它包含一個(gè)特殊的值(很大的值映屋，使它不可能是較小的牌苟鸯，除非兩個(gè)堆都已顯露出其哨兵牌。一旦發(fā)生這種情況棚点，說(shuō)明非哨兵牌都已被放置到輸出堆)早处，用于簡(jiǎn)化代碼。
偽代碼：
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;}}}下面我們來(lái)看一下分治法的步驟
對(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)長(zhǎng)和R數(shù)組已經(jīng)從小到大排好序了，所以找出來(lái)的最小值一定是當(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籍琳，開(kāi)啟下一次循環(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(fǎng)[0]是較小值勋颖，把A[k]即A[1]替換為L(zhǎng)[0]嗦嗡。讓i=i+1，j保存不變饭玲。k=k+1=2侥祭，開(kāi)啟下一次循環(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哀卫，開(kāi)啟下一次循環(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(fǎng)[1]是較小值鼓寺，把A[k]即A[3]替換為L(zhǎng)[1]。讓i=i+1勋磕，j保存不變妈候。k=k+1=4，開(kāi)啟下一次循環(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瑟蜈，開(kāi)啟下一次循環(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(fǎng)[2]是較小值刑顺，把A[k]即A[5]替換為L(zhǎng)[2]氯窍。讓i=i+1，j保存不變蹲堂。k=k+1=6狼讨，開(kāi)啟下一次循環(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è)問(wèn)題呢哀军？試想一下如果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ì)形成長(zhǎng)度為2的排好序的序列，合并長(zhǎng)度為2的序列對(duì)形成長(zhǎng)度為4的排好序的序列蹬叭，依次下去藕咏，直到長(zhǎng)度為n/2的兩個(gè)序列被合并最終形成長(zhǎng)度為n的排好序的序列，數(shù)組最終會(huì)排序完成具垫。
如下圖所示
我們可以把上面提到的MERGE作為歸并排序算法中的一個(gè)子程序來(lái)用侈离。
下面的過(guò)程MERGE-SORT(A,p,r)排序子數(shù)組A[p…r]中的元素试幽。若p>=r,則該子數(shù)組最多有一個(gè)元素筝蚕，所以已經(jīng)排好序。否則铺坞，分解步驟簡(jiǎn)單地計(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é)果}}
下面我們來(lái)看一下歸并排序在數(shù)組A=[5,2,4,7,1,3,2,6]上的操作，隨著算法自底向上地推進(jìn)擒滑，待合并的已排好序的各序列的長(zhǎng)度不斷增加腐晾。
合肥北大青鳥(niǎo)一元校區(qū)是隸屬于北大青鳥(niǎo)旗下的一家IT培訓(xùn)機(jī)構(gòu)，這里有豐富的Java教育資源丐一，完善的教育體系藻糖，和多個(gè)大型企業(yè)擁有合作，學(xué)員學(xué)完課程之后推薦就業(yè)【北大青鳥(niǎo)一元校區(qū) www.kgcbdqn.com】百度搜索“北大青鳥(niǎo)一元校區(qū)”,即可領(lǐng)取試聽(tīng)課程
