## 10.3 分治法 分治法（divide-and-conquer）是解決問題的一種常用策略，其思想是將難以處理的較大 問題分解為若干個較小的子問題，然后分別解決這些子問題，并從子問題的解構造出原問題 的解。“分”是指將原問題分解，“治”是指解決問題。 “分治”僅提及了分而治之的過程，而未提及此方法的另一個特點——遞歸。當我們將 大問題分解成子問題后，經常會發現子問題與大問題本質上是相同的問題，因此可以利用遞 歸方法來設計算法。所以，分治法常常與遞歸法結合起來使用。 下面我們通過排序問題來介紹分治法的應用。排序問題是指將一個數據集合中的所有數 據按從小到大的順序（嚴格遞增或非遞減）重新排列①。計算機科學家發明了很多排序算法， 本節主要介紹利用分而治之思想設計的歸并排序算法，但為了進行比較，我們先介紹沒有什 么“技術含量”的選擇排序算法。 選擇排序 選擇排序是一種樸素的排序方法，普通人都很容易想到。其思想是：先從全體 n 個數據 中找出最小值，并將該最小值排在第一個位置；然后從剩下的 n-1 個數據中再次找出最小值，這個最小值實際上是全體數據的次小值，我們將它排在第二個位置；依此類推，直至從剩下 的 2 個數據中找出最小值，排在第 n-1 個位置，而剩下的最后一個數據（全體數據中的最大 值）可以直接排在第 n 個位置。 > ① 當然也可以按從大到小的順序（嚴格遞減或非遞增）排列，這在解決方法上并沒有什么本質差別。 選擇排序方法的關鍵步驟是找出當前剩余數據中的最小值。我們在 3.6 節中討論過這個 問題①，并且設計了一個很好的算法：逐個檢查每一個數據，并記錄當前見到的最小值；當 數據檢查完畢，所記錄的數據就是全體數據中的最小值。下面我們利用這個求最小值的方法 來實現選擇排序算法。 算法的核心部分是一個循環，每一輪循環找出剩余數據中的最小值，并將該值放到合適 位置。假設數據在列表 list 中，則第一次循環找出 list[0:n-1]中的最小值，并將該值存入 list[0] 處（原來的 list[0]數據需要挪地方，見下面介紹的實現技巧）。第二次循環從 list[1:n-1]中找 出最小值，并存入 list[1]處；依此類推，第 n-1 次循環將 list[n-2:n-1]中的最小值存入 list[n-2]， 而剩下的最后一個數據自然只能存入 list[n-1]。至此，list 中存儲的數據即為從小到大有序 排列的。 實現此算法時，如果沒有額外的存儲空間，只使用 list 本身的空間來排序，則在第一次 循環中將最小值放入 list[0]時，原先存儲在其中的數據就會被覆蓋。為了保留這個數據，一 個簡單的技巧是將 list[0]與找到的最小值交換。即，假如最小值是 list[k]，則執行 ``` list[0],list[k] = list[k],list[0] ``` 其他輪次的處理也是一樣。為此，在循環中需要用一個變量記錄最小值的位置索引。 下面的 Python 代碼實現了以上設計思想，其中每輪循環找出 list[i:n-1]中的最小值（用變量 min 記錄其索引位置），并放入 list[i]中。 ``` >>> def selSort(list): n = len(list) for i in range(n-1): min = i for j in range(i+1,n): if list[j] < list[min]: min = j list[i],list[min] = list[min],list[i] >>> datalist = [5,2,8,3,4] >>> selSort(datalist) >>> print datalist [2, 3, 4, 5, 8] ``` 注意，與 3.6 中最小值算法不同的是，這里找最小值時并非記錄最小值本身，而是記錄最小 值的索引位置 min，即 list[min]才是當前最小值，這是為了使列表數據交換位置更方便。另 外，循環變量 i 只需從 0 取到 n-2，因為當前 n-1 個數據就位后，最后一個位置自然就是最 大值。 選擇排序算法很容易設計實現，并且當數據量不大時效率也還可以，但當數據量很大時 性能很差。采用分治法可以設計一種更好的排序算法，即歸并排序。 > ① 3.6 中討論的是求最大值，但算法稍加改變即可用于求最小值。 歸并排序 人們在玩撲克牌的時候，經常將手上的牌排成特定的順序，比如按花色或按大小排序。 如果分到的牌不多，玩家一般用一只手將牌呈扇形握持，另一只手去整理排序。然而，如果 玩的是用到兩三副牌的游戲，每個玩家分到的牌很多，那么玩家就會有手太小難以排序的煩 惱。這時，如果旁邊坐著個觀戰者，玩家可以請這個觀戰者幫著拿一些牌，兩人分別將手中 不多的牌進行排序，然后再合并兩手牌以完成全部牌的排序。這就是歸并排序的基本思想， 它將大任務分解成較小任務，解決了較小任務后再合并結果。下面我們詳細介紹這種利用分 治法進行排序的方法。 給定一個較大的數據集合 S，先將數據平分為兩部分 S1 和 S2，然后分別對 S1 和 S2 進行 排序，從而得到兩個“局部有序”的序列。接下去將這兩個局部有序序列合并成為“全局有 序”序列，這個過程稱為歸并（merge）。假設用序列 S3 存儲歸并結果，則具體歸并方法是： 第一輪，兩個局部有序的序列 S1 和 S2 分別拿出自己的局部最小值進行比較，其中更小者顯 然是全局最小值，因此應放入 S3 的第一個位置。如果全局最小值來自 S1，則 S1 中原來排在 該最小值后面的數據成為新的局部最小值。第二輪，再次比較 S1 和 S2 的局部最小值，其中 更小者實際上是全局第二小的數據，因此應放入 S3 的第二個位置。第三輪以下依此類推， 不斷比較 S1 和 S2 的局部最小值，并將更小者放入 S3，直至 S1（或 S2）的所有數據都已放入 S3。最后，只需將 S2（或 S1）的剩余數據按序放入 S3 的尾部，即可得到全局有序序列。圖 10.5 用整理撲克牌的例子展示了這個歸并排序過程。   圖 10.5 歸并排序 下面是對圖 10.5 所示過程的簡要解釋： (a) 無序的初始撲克牌集合，牌太多導致難以一手進行排序； (b) 一分為二，玩家和幫忙者兩人各持一半牌； (c) 兩人分別對手中牌進行排序，從而得到兩手局部有序的撲克牌序列； (d) 兩人比較各自手中的局部最小牌（黑桃 2 和方塊 3），其中更小的黑桃 2 是全局最小 牌，將它放到存放歸并結果的某個地方（比如桌子上）； (e)(f)(g) 重復(d)的做法，相繼將方塊 3、梅花 5 和梅花 6 放到歸并結果序列中； (h) 由于第二個序列已經沒有牌了，故將第一個序列剩余的牌接在歸并結果序列之后。 至此形成了全局有序序列。 通過圖 10.5 的形象化演示，相信讀者已經理解歸并過程。現在還有一個問題：圖 10.5(c) 是對圖 10.5(b)的兩手牌分別進行“排序”后得到的，問題是怎么排序？顯然，我們又回到 了初始的“排序”問題，只不過這次的排序問題具有較小的規模：初始問題是對 6 張牌排序， 現在只需兩人分別對自己的 3 張牌排序。這讓我們想起了“遞歸”這個設計利器。是的，如果覺得 3 張牌還是太多，那么可以重復上述一分為二、局部排序、全局歸并的過程。這個過程可以一直進行到只有 1 張牌的情形，這時根本無需排序，因為 1 張牌自然是局部有序的。 這樣就得到了遞歸的奠基情形，此時無需遞歸，只需歸并。由于滿足了每次遞歸數據規模減 小和有奠基情形這兩個條件，上述遞歸過程是正確的。歸并排序算法的偽代碼如下，其中劃 線部分表現了該算法的遞歸結構。 算法：對 datalist 執行歸并排序 輸入：無序的列表 datalist 輸出：有序的列表 datalist 將 datalist 一分為二：list1 和 list2 對 list1 執行歸并排序 對 list2 執行歸并排序 歸并 list1 和 list2，結果放入 datalist 下面我們用 Python 編制一個完整的程序來實現并排序算法。程序 10.1 主要由兩個函數 構成：函數 merge 用于歸并兩個局部有序的列表 list1 和 list2，結果放在 mergelist 中；函數 mergeSort 則利用分治法和遞歸實現對列表 datalist 的排序。 【程序 10.1】mergesort.py ``` def merge(list1,list2,mergelist): i,j,k = 0,0,0 n1,n2 = len(list1),len(list2) while i < n1 and j < n2: if list1[i]&lt;list2[j]: mergelist[k] = list1[i] i = i + 1 else: mergelist[k] = list2[j] j = j + 1 k = k + 1 while i < n1: mergelist[k] = list1[i] i = i + 1 k = k + 1 while j < n2: mergelist[k] = list2[j] j = j + 1 k = k + 1 def mergeSort(datalist): n = len(datalist) if n > 1: m = n / 2 list1,list2 = datalist[:m],datalist[m:] mergeSort(list1) mergeSort(list2) merge(list1,list2,datalist) data = [9,2,7,6,5,3] mergeSort(data) print data ``` 執行程序 10.1，將在屏幕上看到輸出： ``` [2, 3, 5, 6, 7, 9] ``` 順便提醒讀者注意：程序 10.1 中，函數 mergeSort 的形參 datalist 是列表類型，調用時 我們傳遞列表 data 作為實參。由于函數對列表類型的實參的修改后果是可以帶出函數的①， 所以當我們將無序的 data 傳給 mergeSort，等 mergeSort 執行完畢，data 就變成有序的了。 前面介紹的二分搜索算法其實也是分治法的應用，只不過將數據平分為兩部分之后，只 需“治”其中一部分，另一部分可以忽略。后面的 Hanoi 塔問題也是分治法的應用。 最后小結一下分治法。解決一個問題時，經常將問題分解為較小的問題，小問題和大問 題是同類問題。解決了小問題之后，將部分解合并，形成初始問題的最終解。如果小問題完 全類似于初始問題，只是規模較小，顯然可以用遞歸法設計算法。