## 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]<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 塔問題也是分治法的應用。
最后小結一下分治法。解決一個問題時,經常將問題分解為較小的問題,小問題和大問 題是同類問題。解決了小問題之后,將部分解合并,形成初始問題的最終解。如果小問題完 全類似于初始問題,只是規模較小,顯然可以用遞歸法設計算法。
- 前言
- 第 1 章 計算與計算思維
- 1.1 什么是計算?
- 1.1.1 計算機與計算
- 1.1.2 計算機語言
- 1.1.3 算法
- 1.1.4 實現
- 1.2 什么是計算思維?
- 1.2.1 計算思維的基本原則
- 1.2.2 計算思維的具體例子
- 1.2.3 日常生活中的計算思維
- 1.2.4 計算思維對其他學科的影響
- 1.3 初識 Python
- 1.3.1 Python 簡介
- 1.3.2 第一個程序
- 1.3.3 程序的執行方式
- 1.3.4 Python 語言的基本成分
- 1.4 程序排錯
- 1.5 練習
- 第 2 章 用數據表示現實世界
- 2.1 數據和數據類型
- 2.1.1 數據是對現實的抽象
- 2.1.1 常量與變量
- 2.1.2 數據類型
- 2.1.3 Python 的動態類型*
- 2.2 數值類型
- 2.2.1 整數類型 int
- 2.2.2 長整數類型 long
- 2.2.3 浮點數類型 float
- 2.2.4 數學庫模塊 math
- 2.2.5 復數類型 complex*
- 2.3 字符串類型 str
- 2.3.1 字符串類型的字面值形式
- 2.3.2 字符串類型的操作
- 2.3.3 字符的機內表示
- 2.3.4 字符串類型與其他類型的轉換
- 2.3.5 字符串庫 string
- 2.4 布爾類型 bool
- 2.4.1 關系運算
- 2.4.2 邏輯運算
- 2.4.3 布爾代數運算定律*
- 2.4.4 Python 中真假的表示與計算*
- 2.5 列表和元組類型
- 2.5.1 列表類型 list
- 2.5.2 元組類型 tuple
- 2.6 數據的輸入和輸出
- 2.6.1 數據的輸入
- 2.6.2 數據的輸出
- 2.6.3 格式化輸出
- 2.7 編程案例:查找問題
- 2.8 練習
- 第 3 章 數據處理的流程控制
- 3.1 順序控制結構
- 3.2 分支控制結構
- 3.2.1 單分支結構
- 3.2.2 兩路分支結構
- 3.2.3 多路分支結構
- 3.3 異常處理
- 3.3.1 傳統的錯誤檢測方法
- 3.3.2 傳統錯誤檢測方法的缺點
- 3.3.3 異常處理機制
- 3.4 循環控制結構
- 3.4.1 for 循環
- 3.4.2 while 循環
- 3.4.3 循環的非正常中斷
- 3.4.4 嵌套循環
- 3.5 結構化程序設計
- 3.5.1 程序開發過程
- 3.5.2 結構化程序設計的基本內容
- 3.6 編程案例:如何求 n 個數據的最大值?
- 3.6.1 幾種解題策略
- 3.6.2 經驗總結
- 3.7 Python 布爾表達式用作控制結構*
- 3.8 練習
- 第 4 章 模塊化編程
- 4.1 模塊化編程基本概念
- 4.1.1 模塊化設計概述
- 4.1.2 模塊化編程
- 4.1.3 編程語言對模塊化編程的支持
- 4.2 Python 語言中的函數
- 4.2.1 用函數減少重復代碼 首先看一個簡單的用字符畫一棵樹的程序:
- 4.2.2 用函數改善程序結構
- 4.2.3 用函數增強程序的通用性
- 4.2.4 小結:函數的定義與調用
- 4.2.5 變量的作用域
- 4.2.6 函數的返回值
- 4.3 自頂向下設計
- 4.3.1 頂層設計
- 4.3.2 第二層設計
- 4.3.3 第三層設計
- 4.3.4 第四層設計
- 4.3.5 自底向上實現與單元測試
- 4.3.6 開發過程小結
- 4.4 Python 模塊*
- 4.4.1 模塊的創建和使用
- 4.4.2 Python 程序架構
- 4.4.3 標準庫模塊
- 4.4.4 模塊的有條件執行
- 4.5 練習
- 第 5 章 圖形編程
- 5.1 概述
- 5.1.1 計算可視化
- 5.1.2 圖形是復雜數據
- 5.1.3 用對象表示復雜數據
- 5.2 Tkinter 圖形編程
- 5.2.1 導入模塊及創建根窗口
- 5.2.2 創建畫布
- 5.2.3 在畫布上繪圖
- 5.2.4 圖形的事件處理
- 5.3 編程案例
- 5.3.1 統計圖表
- 5.3.2 計算機動畫
- 5.4 軟件的層次化設計:一個案例
- 5.4.1 層次化體系結構
- 5.4.2 案例:圖形庫 graphics
- 5.4.3 graphics 與面向對象
- 5.5 練習
- 第 6 章 大量數據的表示和處理
- 6.1 概述
- 6.2 有序的數據集合體
- 6.2.1 字符串
- 6.2.2 列表
- 6.2.3 元組
- 6.3 無序的數據集合體
- 6.3.1 集合
- 6.3.2 字典
- 6.4 文件
- 6.4.1 文件的基本概念
- 6.4.2 文件操作
- 6.4.3 編程案例:文本文件分析
- 6.4.4 緩沖
- 6.4.5 二進制文件與隨機存取*
- 6.5 幾種高級數據結構*
- 6.5.1 鏈表
- 6.5.2 堆棧
- 6.5.3 隊列
- 6.6 練習
- 第 7 章 面向對象思想與編程
- 7.1 數據與操作:兩種觀點
- 7.1.1 面向過程觀點
- 7.1.2 面向對象觀點
- 7.1.3 類是類型概念的發展
- 7.2 面向對象編程
- 7.2.1 類的定義
- 7.2.2 對象的創建
- 7.2.3 對象方法的調用
- 7.2.4 編程實例:模擬炮彈飛行
- 7.2.5 類與模塊化
- 7.2.6 對象的集合體
- 7.3 超類與子類*
- 7.3.1 繼承
- 7.3.2 覆寫
- 7.3.3 多態性
- 7.4 面向對象設計*
- 7.5 練習
- 第 8 章 圖形用戶界面
- 8.1 圖形用戶界面概述
- 8.1.1 程序的用戶界面
- 8.1.2 圖形界面的組成
- 8.1.3 事件驅動
- 8.2 GUI 編程
- 8.2.1 UI 編程概述
- 8.2.2 初識 Tkinter
- 8.2.3 常見 GUI 構件的用法
- 8.2.4 布局
- 8.2.5 對話框*
- 8.3 Tkinter 事件驅動編程
- 8.3.1 事件和事件對象
- 8.3.2 事件處理
- 8.4 模型-視圖設計方法
- 8.4.1 將 GUI 應用程序封裝成對象
- 8.4.2 模型與視圖
- 8.4.3 編程案例:匯率換算器
- 8.5 練習
- 第 9 章 模擬與并發
- 9.1 模擬
- 9.1.1 計算機建模
- 9.1.2 隨機問題的建模與模擬
- 9.1.3 編程案例:乒乓球比賽模擬
- 9.2 原型法
- 9.3 并行計算*
- 9.3.1 串行、并發與并行
- 9.3.2 進程與線程
- 9.3.3 多線程編程的應用
- 9.3.4 Python 多線程編程
- 9.3.5 小結
- 9.4 練習
- 第 10 章 算法設計和分析
- 10.1 枚舉法
- 10.2 遞歸
- 10.3 分治法
- 10.4 貪心法
- 10.5 算法分析
- 10.5.1 算法復雜度
- 10.5.2 算法分析實例
- 10.6 不可計算的問題
- 10.7 練習
- 第 11 章 計算+X
- 11.1 計算數學
- 11.2 生物信息學
- 11.3 計算物理學
- 11.4 計算化學
- 11.5 計算經濟學
- 11.6 練習
- 附錄
- 1 Python 異常處理參考
- 2 Tkinter 畫布方法
- 3 Tkinter 編程參考
- 3.1 構件屬性值的設置
- 3.2 構件的標準屬性
- 3.3 各種構件的屬性
- 3.4 對話框
- 3.5 事件
- 參考文獻