了得網研究生_算法設計與分析（第2版）

編輯推薦

難度適中，強調算法設計和動手能力培養注重實驗，提供大量的上機實驗題和在線編程題案例來源於著名IT企業面試筆試題和ACM競賽題教學資源豐富，每個知識點都配套了視頻講解

內容簡介

本書繫統地介紹了各種常用的算法設計策略，包括遞歸、分治法、蠻力法、回溯法、分枝限界法、貪心法、動態規劃、概率算法和近似算法等，並詳細討論了各種圖算法和計算幾何設計算法。
全書既注重原理又注重實踐，配有大量圖表、練習題、上機實驗題和在線編程題，內容豐富，概念講解清楚，表達嚴謹，邏輯性強，語言精練，可讀性好。
本書既便於教師課堂講授，又便於自學者閱讀，適合作為高等院校“算法設計與分析”課程的教材，也可供ACM和各類程序設計競賽者參考。

目錄

第1章概論/

1.1算法的概念/

1.1.1什麼是算法/

1.1.2算法描述/

第1章概論/

1.1算法的概念/

1.1.1什麼是算法/

1.1.2算法描述/

1.1.3算法和數據結構/

1.1.4算法設計的基本步驟/

1.2算法分析/

1.2.1算法時間復雜度分析/

1.2.2算法空間復雜度分析/

1.3算法設計工具——STL/

1.3.1STL概述/

1.3.2常用的STL容器/

1.3.3STL在算法設計中的應用/

1.4練習題/

1.5上機實驗題/

1.6在線編程題/

第2章遞歸算法設計技術/

2.1什麼是遞歸/

2.1.1遞歸的定義/

2.1.2何時使用遞歸/

2.1.3遞歸模型/

2.1.4遞歸算法的執行過程/

2.2遞歸算法設計/

2.2.1遞歸與數學歸納法/

2.2.2遞歸算法設計的一般步驟/

2.2.3遞歸數據結構及其遞歸算法設計/

2.2.4基於歸納思想的遞歸算法設計/

2.3遞歸算法設計示例/

2.3.1簡單選擇排序和冒泡排序/

2.3.2求解n皇後問題/

2.4*遞歸算法轉化為非遞歸算法/

2.4.1用循環結構替代遞歸過程/

2.4.2用棧消除遞歸過程/

2.5遞推式的計算/

2.5.1用特征方程求解遞歸方程/

2.5.2用遞歸樹求解遞歸方程/

2.5.3用主方法求解遞歸方程/

2.6練習題/

2.7上機實驗題/

2.8在線編程題/

第3章分治法/

3.1分治法概述/

3.1.1分治法的設計思想/

3.1.2分治法的求解過程/

3.2求解排序問題/

3.2.1快速排序/

3.2.2歸並排序/

3.3求解查找問題/

3.3.1查找素/

3.3.2折半查找/

3.3.3尋找一個序列中第素/

3.3.4尋找兩個等長有序序列的中位數/

3.4求解組合問題/

3.4.1求解連續子序列和問題/

3.4.2求解棋盤覆蓋問題/

3.4.3求解循環日程安排問題/

3.5求解大整數乘法和矩陣乘法問題/

3.5.1求解大整數乘法問題/

3.5.2求解矩陣乘法問題/

3.6並行計算簡介/

3.6.1並行計算概述/

3.6.2並行計算模型/

3.6.3快速排序的並行算法/

3.7練習題/

3.8上機實驗題/

3.9在線編程題/

第4章蠻力法/

4.1蠻力法概述/

4.2蠻力法的基本應用/

4.2.1采用直接窮舉思路的一般格式/

4.2.2簡單選擇排序和冒泡排序/

4.2.3字符串匹配/

4.2.4求解連續子序列和問題/

4.2.5求解冪集問題/

4.2.6求解簡單0/1背包問題/

4.2.7求解全排列問題/

4.2.8求解任務分配問題/

4.3遞歸在蠻力法中的應用/

4.3.1用遞歸方法求解冪集問題/

4.3.2用遞歸方法求解全排列問題/

4.3.3用遞歸方法求解組合問題/

4.4圖的深度優先和廣度優先遍歷/

4.4.1圖的存儲結構/

4.4.2深度優先遍歷/

4.4.3廣度優先遍歷/

4.4.4求解迷宮問題/

4.5練習題/

4.6上機實驗題/

4.7在線編程題/

第5章回溯法/

5.1回溯法概述/

5.1.1問題的解空間/

5.1.2什麼是回溯法/

5.1.3回溯法的算法框架及其應用/

5.1.4回溯法與深度優先遍歷的異同/

5.1.5回溯法的時間分析/

5.2求解0/1背包問題/

5.3求解裝載問題/

5.3.1求解簡單裝載問題/

5.3.2求解復雜裝載問題/

5.4求解子集和問題/

5.4.1求子集和問題的解/

5.4.2判斷子集和問題是否存在解/

5.5求解n皇後問題/

5.6求解圖的m著色問題/

5.7求解任務分配問題/

5.8求解活動安排問題/

5.9求解流水作業調度問題/

5.10練習題/

5.11上機實驗題/

5.12在線編程題/

第6章分枝限界法/

6.1分枝限界法概述/

6.1.1什麼是分枝限界法/

6.1.2分枝限界法的設計思想/

6.1.3分枝限界法的時間性能/

6.2求解0/1背包問題/

6.2.1采用隊列式分枝限界法求解/

6.2.2采用優先隊列式分枝限界法求解/

6.3求解圖的單源短路徑/

6.3.1采用隊列式分枝限界法求解/

6.3.2采用優先隊列式分枝限界法求解/

6.4求解任務分配問題/

6.5求解流水作業調度問題/

6.6練習題/

6.7上機實驗題/

6.8在線編程題/

第7章貪心法/

7.1貪心法概述/

7.1.1什麼是貪心法/

7.1.2用貪心法求解的問題應具有的性質/

7.1.3貪心法的一般求解過程/

7.2求解活動安排問題/

7.3求解背包問題/

7.4求解裝載問題/

7.5求解田忌賽馬問題/

7.6求解多機調度問題/

7.7哈夫曼編碼/

7.8求解流水作業調度問題/

7.9練習題/

7.10上機實驗題/

7.11在線編程題/

第8章動態規劃/

8.1動態規劃概述/

8.1.1從求解斐波那契數列看動態規劃法/

8.1.2動態規劃的原理/

8.1.3動態規劃求解的基本步驟/

8.1.4動態規劃與其他方法的比較/

8.2求解整數拆分問題/

8.3求解連續子序列和問題/

8.4求解三角形小路徑問題/

8.5求解長公共子序列問題/

8.6求解長遞增子序列問題/

8.7求解編輯距離問題/

8.8求解0/1背包問題/

8.9求解完全背包問題/

8.10求解資源分配問題/

8.11求解會議安排問題/

8.12滾動數組/

8.12.1什麼是滾動數組/

8.12.2用滾動數組求解0/1背包問題/

8.13練習題/

8.14上機實驗題/

8.15在線編程題/

第9章圖算法設計/

9.1求圖的小生成樹/

9.1.1小生成樹的概念/

9.1.2用普裡姆算法構造小生成樹/

9.1.3克魯斯卡爾算法/

9.2求圖的短路徑/

9.2.1狄克斯特拉算法/

9.2.2貝爾曼福特算法/

9.2.3SPFA算法/

9.2.4弗洛伊德算法/

9.3求解旅行商問題/

9.3.1旅行商問題描述/

9.3.2采用蠻力法求解TSP問題/

9.3.3采用動態規劃求解TSP問題/

9.3.4采用回溯法求解TSP問題/

9.3.5采用分枝限界法求解TSP問題/

9.3.6采用貪心法求解TSP問題/

9.4網絡流/

9.4.1相關概念/

9.4.2求流/

9.4.3割集與割量/

9.4.4求小費用流/

9.5練習題/

9.6上機實驗題/

9.7在線編程題/

第10章計算幾何/

10.1向量運算/

10.1.1向量的基本運算/

10.1.2判斷一個點是否在一個矩形內/

10.1.3判斷一個點是否在一條線段上/

10.1.4判斷兩條線段是否平行/

10.1.5判斷兩條線段是否相交/

10.1.6判斷一個點是否在多邊形內/

10.1.7求3個點構成的三角形的面積/

10.1.8求一個多邊形的面積/

10.2求解凸包問題/

10.2.1禮品包裹算法/

10.2.2Graham掃描算法/

10.3求解近點對問題/

10.3.1用蠻力法求近點對/

10.3.2用分治法求近點對/

10.4求解遠點對問題/

10.4.1用蠻力法求遠點對/

10.4.2用旋轉卡殼法求遠點對/

10.5練習題/

10.6上機實驗題/

10.7在線編程題/

第11章計算復雜性理論簡介/

11.1計算模型/

11.1.1求解問題的分類/

11.1.2圖靈機模型/

11.2P類和NP類問題/

11.3NPC問題/

11.4練習題/

第12章概率算法和近似算法/

12.1概率算法/

12.1.1什麼是概率算法/

12.1.2蒙特卡羅類型概率算法/

12.1.3拉斯維加斯類型概率算法/

12.1.4舍伍德類型概率算法/

12.2近似算法/

12.2.1什麼是近似算法/

12.2.2求解旅行商問題的近似算法/

12.3練習題/

12.4上機實驗題/

12.5在線編程題/

附錄A書中部分算法清單/

參考文獻/

前言

前言

前言
算法在計算科學中扮演著重要角色。算法設計是計算機科學與技術專業的必修課，其目標是培養學生分析問題和解決問題的能力，使學生掌握算法設計的基本技巧和方法，熟悉算法分析的基本技術，並能熟練運用一些常用算法策略解決一些較綜合的問題。在學習本書之前，學生已經學習了基本的數據結構知識，能熟練運用一門或多門編程語言，並具備了一定的編程經驗。如何利用已學過的知識針對不同的實際問題設計出有效的算法，是本書所要達到的目的。本書的特點是“問題模型化，求解算法化，設計化”，在掌握必要的算法設計技術和編程技巧的基礎上，能夠在實際工作中根據具體問題設計和優化算法。本書是針對這一特點並結合課程組全體教師多年的教學經驗編寫的。1. 本書內容全書由12章構成，各章的內容如下。第1章概論：介紹算法的概念、算法分析方法和STL在算法設計中的應用。第2章遞歸算法設計技術：介紹遞歸的概念、遞歸算法設計方法和相關示例、遞歸算法到非遞歸算法的轉化以及遞推式的計算。第3章分治法：介紹分治法的策略和求解過程，討論采用分治法求解排序問題、查找問題、連續子序列和問題、大整數乘法問題及矩陣乘法問題的典型算法，並簡要介紹了並行計算的概念。第4章蠻力法：介紹蠻力法的特點、蠻力法的基本應用示例、遞歸在蠻力法中的應用以及圖的深度優先和廣度優先遍歷算法。第5章回溯法：介紹解空間概念和回溯法算法框架，討論采用回溯法求解0/1背包問題、裝載問題、子集和問題、n皇後問題、圖的m著色問題、任務分配問題、活動安排問題和流水作業調度問題的典型算法。第6章分枝限界法：介紹分枝限界法的特點和算法框架、隊列式分枝限界法和優先隊列式分枝限界法，討論采用分枝限界法求解0/1背包問題、圖的單源短路徑、任務分配問題和流水作業調度問題的典型算法。第7章貪心法：介紹貪心法的策略、求解過程和貪心法求解問題應具有的性質，討論采用貪心法求解活動安排問題、背包問題、裝載問題、田忌賽馬問題、多機調度問題、哈夫曼編碼和流水作業調度問題的典型算法。第8章動態規劃：介紹動態規劃的原理和求解步驟，討論采用動態規劃法求解整數拆分問題、連續子序列和問題、三角形小路徑問題、長公共子序列問題、長遞增子序列問題、編輯距離問題、0/1背包問題、完全背包問題、資源分配問題、會議安排問題和滾動數組的典型算法。第9章圖算法設計：討論構造圖小生成樹的兩種算法(Prim和Kruskal算法，並查集的應用)、求圖的短路徑的4種算法(Dijkstra、BellmanFord、SPFA和Floyd)，並采用5種算法策略求解旅行商問題(TSP問題)，後介紹網絡流的相關概念以及求流和小費用流的算法。第10章計算幾何：介紹計算幾何中常用的矢量運算以及求解凸包問題、近點對問題和遠點對問題的典型算法。第11章計算復雜性理論簡介：介紹圖靈機計算模型、P類和NP類問題以及NPC問題。第12章概率算法和近似算法：介紹這兩類算法的特點和基本的算法設計方法。書中帶“*”符號的章節作為選學內容。2. 本書特色本書具有如下鮮明特色。(1) 由淺入深，循序漸進：每種算法策略從設計思想、算法框架入手，由易到難地講解經典問題的求解過程，使讀者既能學到求解問題的方法，又能通過對算法策略的反復應用掌握其核心原理，以收到融會貫通之效。(2) 示例豐富，重視啟發：書中列舉大量的具有典型性的求解問題，深入剖析采用相關算法策略求解的思路，展示算法設計的清晰過程，並舉一反三，激發學生學習算法設計的興趣。(3) 注重求解問題的多維性：同一個問題采用多種算法策略實現，如0/1背包問題采用回溯法、分枝限界法和動態規劃求解，旅行商問題采用5種算法策略求解。通過不同算法策略的比較，使學生更容易體會到每一種算法策略的設計特點和各自的優/缺點，以提高算法設計的效率。(4) 強調實驗和動手能力的培養：算法講解不僅包含思路描述，而且以C/C 完整程序的形式呈現，同時給出了大量的上機實驗題和在線編程題，大部分是近幾年國內外的著名IT企業面試筆試題(谷歌、微軟、阿裡巴巴、騰訊、網易等)和ACM競賽題。通過這些題目的訓練，不僅可以提高學生的編程能力，而且可以幫助其直面求職市場。（5）本書配套有《算法設計與分析（第2版）學習與實驗指導》（李春葆，清華大學出版社，2018），涵蓋所有練習題、上機實驗題和在線編程題的參考答案。（6）本書配套有絕大部分知識點的教學視頻，視頻采用微課碎片化形式組織（含100多個小視頻，累計超過20小時），讀者通過掃描二維碼即可觀看相關視頻講解。3. 教學資源本書提供的教學資源包括完整的教學PPT和書中全部源程序代碼(在VC 6．0中調試通過)，用戶可以掃描封底課件二維碼免費下載。4. 感謝本書的編寫得到湖北省教育廳和武漢大學教學研究項目《計算機科學與技術專業課程體繫改革》的大力幫助，清華大學出版社的魏江江主任全力支持本書的編寫工作，王冰飛老師給予精心的編輯工作。本書在編寫過程中參考了很多同行的教材和網絡博客，特別是“牛客網”中眾多的企業面試、筆試題和豐富資源給予編者良好的啟發，河南工程學院張天伍老師和使用本教材第1版的多位老師指正多處問題和錯誤，在此一並表示衷心感謝。本書是課程組全體教師多年教學經驗的總結和體現，盡管編者不遺餘力，但由於水平所限，難免存在不足之處，敬請教師和同學們批評指正，在此表示衷心感謝。編者
2018年5月

在線試讀

第3章分治法

第3章分治法

分治法是使用廣泛的算法設計方法之一。其基本策略是采用遞歸思想把大問題分解成一些小問題，然後由小問題的解方便地構造出大問題的解。本章介紹分治法求解問題的一般方法，並給出一些用分治法求解的經典示例。3.1分治法概述3.1.1分治法的設計思想對於一個規模為n的問題，若該問題可以容易地解決(例如規模n較小)則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解，這種算法設計策略叫分治法。如果原問題可分割成k(1

divideandconquer(P)
{if |P|≤n0 return adhoc(P);
將P分解為較小的子問題 P1、P2、…、Pk;
for(i=1;i<=k;i )//循環處理k次
yi=divideandconquer(Pi);//遞歸解決Pi
return merge(y1,y2,…,yk);//合並子問題
}

其中，|P|表示問題P的規模； n0為一閾值，表示當問題P的規模不超過n0時(即P問題規模足夠小時)已容易直接解出，不必再繼續分解。adhoc(P)是該分治法中的基本子算法，用於直接解小規模的問題P。算法merge(y1，y2，…，yk)是該分治法中的合並子算法，用於將P的子問題P1、P2、…、Pk的相應解y1、y2、…、yk合並為P的解。根據分治法的分解原則，原問題應該分解為多少個子問題纔較適合？各個子問題的規模應該怎樣纔為適當？這些問題很難給予肯定的回答。但人們從大量

圖3.1二分法的基本策略

的實踐中發現，在用分治法設計算法時好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。當k=1時稱為減治法。許多問題可以取k=2，稱為二分法，如圖3.1所示，這種使子問題規模大致相等的做法出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。
分治法的合並步驟是算法的關鍵所在。有些問題的合並方法比較明顯，有些問題的合並方法比較復雜，或者是有多種合並方案；或者是合並方案不明顯。究竟應該怎樣合並沒有統一的模式，需要具體問題具體分析。盡管許多分治法算法都是采用遞歸實現的，但要注意分治法和遞歸是有區別的，分治法是一種求解問題的策略，而遞歸是一種實現求解算法的技術。分治法算法也可以采用非遞歸方法實現。就像二分查找，作為一種典型的分治法算法，既可以采用遞歸實現，也可以采用非遞歸實現。3.2求解排序問題對於給定的含素的數組a，素值遞增排序。快速排序和歸並排序是典型的采用分治法進行排序的方法。3.2.1快速排序
快速排序的基本思想是在待排序素中任素(通素)作為基準素放入終位置後，整個數據序列被基準分割成兩個子序列，所有小於素放置在前子序列中，所有大於素放置在後子序列中，並把基準排在這兩個子序列的中間，這個過程稱為劃分，如圖3.2所示。然後對兩個子序列分別重復上述過程，直到每個子序列內隻素或空為止。

圖3.2快速排序的一趟排序過程

這是一種二分法思想，每次將整個無序序列一分為二，歸素，對兩個子序列采用同樣的方式進行排序，直到子序列的長度為1或0為止。快速排序的分治策略如下。(1) 分解：將原序列a［s..t］分解成兩個子序列a［s..i-1］和a［i 1..t］，其中i為劃分的基準位置，即將整個問題分解為兩個子問題。(2) 求解子問題：若子序列的長度為0或1，則它是有序的，直接返回；否則遞歸地求解各個子問題。(3) 合並：由於整個序列存放在數組a中，排序過程是就地進行的，合並步驟不需要執行任何操作。例如，對於(2，5，1，7，10，6，9，4，3，8)序列，其快速排序過程如圖3.3所示，圖中虛線表示一次劃分，虛線旁的數字表示執行次序，圓圈表示歸位的基準。

圖3.3(2，5，1，7，10，6，9，4，3，8)序列的快速排序過程

實現快速排序的完整程序如下：

#include
void disp(int a［］,int n)//輸出a中素
{int i;
for (i=0;iprintf("%d ",a［i］);
printf("＼n");
}
int Partition(int a［］,int s,int t)//劃分算法
{int i=s,j=t;
int tmp=a［s］;//用序列的第1個記錄作為基準
while (i!=j)//從序列兩端交替向中間掃描,直到i=j為止
{while (j>i && a［j］>=tmp)
j--;//從右向左掃描,找第1個關鍵字小於tmp的a［j］
a［i］=a［j］;//將a［j］前移到a［i］的位置
while (ii ;//從左向右掃描,找第1個關鍵字大於tmp的a［i］
a［j］=a［i］;//將a［i］後移到a［j］的位置
}
a［i］=tmp;
return i;
}
void QuickSort(int a［］,int s,int t)//對a［s.素序列進行遞增排序
{if (s{int i=Partition(a,s,t);
QuickSort(a,s,i-1);//對左子序列遞歸排序
QuickSort(a,i 1,t);//對右子序列遞歸排序
}
}
void main()
{int n=10;
int a［］={2,5,1,7,10,6,9,4,3,8};
printf("排序前:"); disp(a,n);
QuickSort(a,0,n-1);
printf("排序後:"); disp(a,n);
}

【算法分析】快速排序的時間主要耗費在劃分操作上，對長度為n的區間進行劃分，共需n-1次關鍵字的比較，時間復雜度為O(n)。素進行快速排序的過程構成一棵遞歸樹，在這樣的遞歸樹中，每一層多素進行劃分，所花的時間為O(n)。當初始排序數據正序或反序時，遞歸樹高度為n，快速排序呈現壞情況，即壞情況下的時間復雜度為O(n2)；當初始排序數據隨機分布，使每次分成的兩個子區素個數大致相等時，遞歸樹高度為log2n，快速排序呈現好情況，即好情況下的時間復雜度為O(nlog2n)。快速排序算法的平均時間復雜度也是O(nlog2n)。所以快速排序是一種高效的算法，STL中的sort()算法就是采用快速排序方法實現的。3.2.2歸並排序
歸並排序的基本思想是首先將a［0..n-1］看成n個長度為1的有序表，將相鄰的k(k≥2)個有序子表成對歸並，得到n/k個長度為k的有序子表；然後再將這些有序子表繼續歸並，得到n/k2個長度為k2的有序子表，如此反復進行下去，後得到一個長度為n的有序表。由於整個排序結果放在一個數組中，所以不需要特別地進行合並操作。若k=2，即歸並是在相鄰的兩個有序子表中進行的，稱為二路歸並排序。若k>2，即歸並操作在相鄰的多個有序子表中進行，則叫多路歸並排序。這裡僅討論二路歸並排序算法，二路歸並排序算法主要有兩種，下面一一討論。1. 自底向上的二路歸並排序算法自底向上的二路歸並算法采用歸並排序的基本原理，第1趟歸並排序時將待排序的表a［0..n-1］看作是n個長度為1的有序子表，將這些子表兩兩歸並，若n為偶數，則得到n/2個長度為2的有序子表；若n為奇數，則後一個子表輪空(不參與歸並)，故本趟歸並完成後，前n/2-1個有序子表長度為2，但後一個子表長度仍為1；第2趟歸並則是將第1趟歸並所得到的n/2個有序子表兩兩歸並，如此反復，直到後得到一個長度為n的有序表為止。首先設計算法Merge()用於將兩個有序子表歸並為一個有序子表。設兩個有序子表存放在同一個表中相鄰的位置上，即a［low..mid］(有mid-low素)、a［mid 1..high］(有high-m素)，先將它們合並到一個臨時表tmpa［0..high-low］中，在合並完成後將tmpa復制到a中。其歸並過程是循環從兩個子表中順序取素進行比較，並將較小者放到tmpa中，當一素取完時將另一個子表中餘下的部分直接復制到tmpa中。這樣tmpa是一個有序表，再將其復制到a中。其次，設計算法MergePass()通過調用Merge()算法解決一趟歸並問題。在某趟歸並中，設各子表長度為length(後一個子表的長度可能小於length)，則歸並前a［0..n-1］中共nlength個有序子表，即a［0..1ength-1］、a［length..2length-1］、…、anlengthlength..n-1。調用Merge()一次將相鄰的一對子表進行歸並，另外需要對表的個數可能是奇數以及後一個子表的長度小於length這兩種特殊情況進行處理：若子表的個數為奇數，則後一個子表無須和其他子表歸並(即本趟輪空)；若子表的個數為偶數，則要注意到後一對子表中後一個子表的區間上界是n-1。後，對於含素的序列a，設計算法MergeSort()調用MergePass()算法log2n次實現二路歸並排序。二路歸並排序的分治策略如下：循環log2n次，length依次取1、2、…、log2n，每次執行以下步驟。(1) 分解：將原序列分解成length長度的若干個子序列。(2) 求解子問題：對相鄰的兩個子序列調用Merge算法合並成一個有序子序列。(3) 合並：由於整個序列存放在數組a中，排序過程是就地進行的，合並步驟不需要執行任何操作。例如，對於(2，5，1，7，10，6，9，4，3，8)序列，其排序過程如圖3.4所示，圖中方括號內是一個有序子序列。

圖3.4自底向上的二路歸並排序過程

實現二路歸並排序的完整程序如下：

#include
#include
void disp(int a［］,int n)//輸出a中素
{int i;
for (i=0;iprintf("%d ",a［i］);
printf("＼n");
}
void Merge(int a［］,int low,int mid,int high)
//將a［low..mid］和a［mid 1..high］兩個相鄰的有序子序列歸並為一個有序子序列a［low..high］
{int *tmpa;
int i=low,j=mid 1,k=0;//k是tmpa的下標,i、j分別為兩個子表的下標
tmpa=(int *)malloc((highlow 1)*sizeof(int));
while (i<=mid && j<=high)//在第1個子表和第2個子表均未掃描完時循環
if (a［i］<=a［j］)//將第1個子素放入tmpa中
{tmpa［k］=a［i］;
i ;k ;
}
else//將第2個子素放入tmpa中
{tmpa［k］=a［j］;
j ;k ;
}
while (i<=mid)//將第1個子表餘下的部分復制到tmpa
{tmpa［k］=a［i］;
i ;k ;
}
while (j<=high)//將第2個子表餘下的部分復制到tmpa
{tmpa［k］=a［j］;
j ;k ;
}
for (k=0,i=low;i<=high;k ,i ) //將tmpa復制回a中
a［i］=tmpa［k］;
free(tmpa);//釋放臨時空間
}

void MergePass(int a［］,int length,int n)//一趟二路歸並排序
{int i;
for (i=0;i 2*length-1Merge(a,i,i length-1,i 2*length-1);
if (i length-1Merge(a,i,i length-1,n-1);//歸並這兩個子表
}
void MergeSort(int a［］,int n)//二路歸並算法
{int length;
for (length=1;lengthMergePass(a,length,n);
}
void main()
{int n=10;
int a［］={2,5,1,7,10,6,9,4,3,8};
printf("排序前:"); disp(a,n);
MergeSort(a,n);
printf("排序後:"); disp(a,n);
}

【算法分析】對於上述二路歸並排序算法，當素時需要log2n趟歸並，每一趟歸素比較次數不超過n素移動次數都是n，因此二路歸並排序的時間復雜度為O(nlog2n)。2. 自頂向下的二路歸並排序算法上述自底向上的二路歸並算法雖然效率較高，但可讀性較差。另一種是采用自頂向下的方法設計，算法更為簡潔，屬典型的二分法算法。設歸並排序的當前區間是a［low..high］，則遞歸歸並的步驟如下。(1) 分解：將當前序列a［low..high］一分為二，即求mid=(low high)/2，分解為兩個子序列a［low..mid］和a［mid 1..high］。(2) 子問題求解：遞歸地對兩個子序列a［low..mid］和a［mid 1..high］二路歸並排序。其終結條件是子序列的長度為1或者0(因素的子表或者空表可以看成有序表)。(3) 合並：與分解過程相反，將已排序的兩個子序列a［low..mid］和a［mid 1..high］歸並為一個有序序列a［low..high］。對應的二路歸並排序算法如下：

void MergeSort(int a［］,int low,int high)//二路歸並算法
{int mid;
if (low{mid=(low high)/2;//取中間位置
MergeSort(a,low,mid);//對a［low..mid］子序列排序
MergeSort(a,mid 1,high);//對a［mid 1..high］子序列排序
Merge(a,low,mid,high);//將兩個子序列合並,見前面的算法
}
}

例如，對於(2，5，1，7，10，6，9，4，3，8)序列，其排序過程如圖3.5所示，圖中圓括號內的數字指出操作順序。

圖3.5自頂向下的二路歸並排序過程

【算法分析】設MergeSort(a，0，n-1)算法的執行時間為T(n)，顯然Merge(a，0，n/2，n-1)合並操作的執行時間為O(n)，所以得到以下遞推式：

T(n)=1當n=1時
T(n)=2T(n/2) O(n)當n>1時

容易推出T(n)=O(nlog2n)。3.3求解查找問題3.3.1查找素
【問題描述】對於給定的含素的無序序列，求這個序列中和次大的兩素。【問題求解】對於無序序列a［low..high］，采用分素max1素max2的過程如下： (1) 若a［low..high］中隻素，則max1=a［low］，max2=-INF(-∞)。(2) 若a［low..high］中隻素，則max1=max{a［low］，a［high］}，max2=min{a［low］，a［high］}。(3) 若a［low..high］中有兩素，按中間位置mid=(low high)/2劃分為a［low..mid］和a［mid 1..high］兩個區間(注意左區間包含a［m素)。求出左素lmax1素lmax2，求出右素rmax1素rmax2。若lmax1>rmax1，則max1=lmax1，max2=max{lmax2，rmax1}；否則max1=rmax1，max2=max{lmax1，rmax2}。例如，對於a［0..4］={5，2，1，4，3}，mid=(0 4)/2=2，劃分為左區間a［0..2］={5，2，1}，右區間a［3..4］={4，3}。在左區間中求出lmax1=5，lmax2=2，在右區間中求出rmax1=4，rmax2=3。所以max1=max{lmax1，rmax1}=5，max2=max{lmax2，rmax1}=4。對應的算法如下：

void solve(int a［］,int low,int high,int &max1,int &max2)
{if (low==high)//區間中隻素
{max1=a［low］;
max2=-INF;
}
else if (low==high-1)//區間中隻素
{max1=max(a［low］,a［high］);
max2=min(a［low］,a［high］);
}
else//區間中有兩素
{int mid=(low high)/2;
int lmax1,lmax2;
solve(a,low,mid,lmax1,lmax2);//左區間求lmax1和lmax2
int rmax1,rmax2;
solve(a,mid 1,high,rmax1,rmax2);//右區間求rmax1和rmax2
if (lmax1>rmax1)
{max1=lmax1;
max2=max(lmax2,rmax1);//lmax2、rmax1中素
}
else
{max1=rmax1;
max2=max(lmax1,rmax2);//lmax1、rmax2中素
}
}
}

【算法分析】對於solve(a，0，n-1，max1，max2)調用，其比較次數的遞推式如下：

T(1)=T(2)=1
T(n)=2T(n/2) 1//合並的時間為O(1)

可以推導出T(n)=O(n)。3.3.2折半查找
折半查找又稱二分查找，它是一種效率較高的查找方法。但是折半查找要求查找序素是有序的，為了簡單，假設是遞增有序的。折半查找的基本思路：設a［low..high］是當前的查找區間，首先確定該區間的中點位置mid=(low high)/2；然後將待查的k值與a［mid］.key比較。(1) 若k==a［mid］.key，則查找成功並素的物理下標。(2) 若ka［mid］，則要查找的k必定位於右子表a［mid 1..high］中，即新的查找區間是右子表a［mid 1..high］。下一次查找是針對新的查找區間進行的。因此可以從初始的查找區間a［0..n-1］開始，每經過一次與當前查找區間的中點位置上的關鍵字比較就可確定查找是否成功，不成功則當前的查找區間縮小一半。重復這一過程，直到找到關鍵字素，或者直到當前的查找區間為空(即查找失敗)時為止。折半查找對應的完整程序如下：

#include
int BinSearch(int a［］,int low,int high,int k)//折半查找算法
{int mid;
if (low<=high)//當前區素時
{mid=(low high)/2;//求查找區間的中間位置
if (a［mid］==k)//找到後返回其物理下標mid
return mid;
if (a［mid］>k)//當a［mid］>k時在a［low..mid-1］中遞歸查找
return BinSearch(a,low,mid-1,k);
else//當a［mid］return BinSearch(a,mid 1,high,k);
}
else return -1;//當前查找區素時返回-1
}
void main()
{int n=10,i;
int k=6;
int a［］={1,2,3,4,5,6,7,8,9,10};
i=BinSearch(a,0,n-1,k);
if (i>=0)printf("a［%d］=%d＼n",i,k);
else printf("未找素＼n",k);
}

可以將折半查找遞歸算法等價地轉換成以下非遞歸算法：

int BinSearch1(int a［］,int n,int k)//非遞歸折半查找算法
{int low=0,high=n-1,mid;

while (low<=high)//當前區素時循環
{mid=(low high)/2;//求查找區間的中間位置
if (a［mid］==k)//找到後返回其物理下標mid
return mid;
if (a［mid］>k)//繼續在a［low..mid-1］中查找
high=mid-1;
else//a［mid］low=mid 1;//繼續在a［mid 1..high］中查找
}
return -1;//當前查找區素時返回-1
}

【算法分析】折半查找算法的主要時間素的比較上，對於含素的有序表，采用折半查找時壞情素比較次數為C(n)，則有：

C(n)=1當n=1時
C(n)≤1 C(n/2)當n≥2時

設對某個整數k≥2，滿足2k-1≤n＜2k。展開上述遞推式，可得到：

C(n)≤1 C(n/2)
≤2＋Cn/4)
…
≤(k-1) Cn/2k-1)
=(k-1) 1
=k

而2k-1≤n＜2k，即k≤log2n 1＜k 1，k=log2n 1。由此得到C(n)≤log2n 1。也就是說，在含素的有序序列中采用折半查找算法查找素素比較次數不超過log2n 1(或者log2(n 1))。實際上素的折半查找對應判定樹的高度恰好是log2n 1。折半查找的主要時素的比較上，所以算法的時間復雜度為O(log2n)。折半查找的思路很容易推廣到三分查找，顯然三分查找對應判斷樹的高度恰好是log3n 1，推出查找時間復雜度為O(log3n)，由於log3n=log2n/log23，所以三分查找和二分查找的時間是同一個數量級的。【例3.1】求解問題。有100個硬幣，其中有一個(與真幣一模一樣，隻是比真幣的重量輕)，采用天平稱重方法找出這個，少用天平稱重多少次保證找出。解已知比真幣的重量輕，可以將100個硬幣分為兩組，每組50個硬幣，稱重一次可以確定所在的組，即二分法。更好的方法是采用三分法，將100個硬幣分為33、33、34三組，用天平一次稱重可以找出所在的組，依次進行，對應一棵三分判定樹，樹高度恰好是稱重次數，結果為log3(100 1)=5。3.3.3尋找一個序列中第素【問題描述】對於給定的含素的無序序列，求這個序列中第k(1≤k≤n素。【問題求解】假設無序序列存放在a［0..n-1］中，若將a遞增排序，則第素為a［k-1］。采用類似快速排序的思想。
對於無序序列a［s..t］，在其中查找第素的過程如下： (1) 若s≥t，即其中隻素或沒素，如果s=t且s=k-1，表示隻素且a［k-1］就是要求的結果，返回a［k-1］。(2) 若si，第素應在a［i 1..t］子序列中，遞歸在該子序列中求解並返回其結果。對應的完整程序如下：

#include
int QuickSelect(int a［］,int s,int t,int k)//在a［s..t］序列中找第素
{int i=s,j=t;
int tmp;
if (s{tmp=a［s］;//用區間的第1個記錄作為基準
while (i!=j)//從區間兩端交替向中間掃描,直到i=j為止
{while (j>i && a［j］>=tmp)
j--;//從右向左掃描,找第1個關鍵字小於tmp的a［j］
a［i］=a［j］;//將a［j］前移到a［i］的位置
while (ii ;//從左向右掃描,找第1個關鍵字大於tmp的a［i］
a［j］=a［i］;//將a［i］後移到a［j］的位置
}
a［i］=tmp;
if (k-1==i) return a［i］;
else if (k-1else return QuickSelect(a,i 1,t,k);//在右區間中遞歸查找
}
else if (s==t && s==k-1)//區間內隻素且為a［k-1］
return a［k-1］;
}
void main()
{int n=10,k;
int e;
int a［］={2,5,1,7,10,6,9,4,3,8};
for (k=1;k<=n;k )
{e=QuickSelect(a,0,n-1,k);
printf("第%素:%d＼n",k,e);
}
}

本程序的執行結果如下：

第素:1
第素:2
第素:3
第素:4
第素:5
第素:6
第素:7
第素:8
第素:9
第1素:10

【算法分析】對於QuickSelect(a，s，t，k)算法，設序列a中含素，其比較次數的遞推式為：

T(n)=T(n/2) O(n)

可以推導出T(n)=O(n)，這是好的情況，即每次劃分的基準恰好是中位數，將一個序列劃分為長度大致相等的兩個子序列。在壞情況下，每次劃分的基準恰好是序列中的值或小值，則處理區間隻比上一次減素，此時比較次數為O(n2)。在平均情況下該算法的時間復雜度為O(n)。3.3.4尋找兩個等長有序序列的中位數
【問題描述】對於一個長度為n的有序序列(假設均為升序序列)a［0..n-1］，處於中間素稱為a的中位數。例如，若序列a=(11，13，15，17，19)，其中位數是15，若b=(2，4，6，8，20)，其中位數為6。兩個等長有序序列的中位數是含它素的有序序列的中位數，例如a、b兩個有序序列的中位數為11。設計一個算法求給定的兩個有序序列的中位數。【問題求解】對於含素的有序序列a［s..t］，當n為奇數時，中位數出現在m=(s t)/2處；當n為偶數時，中位數下標有m=(s t)/2(下中位)和m=(s t)/2 1(上中位)兩個。為了簡單，這裡僅考慮中位數下標為m=(s t)/2。采用二分法求含有n素的序列a、b的中位數的過程如下： (1) 分別求出a、b的中位數a［m1］和b［m2］。(2) 若a［m1］=b［m2］，則a［m1］或b［m2］即為所求中位數，如圖3.6(a)所示，算法結束。 (3) 若a［m1］b［m2］，則舍棄序列a中的後半部分(較大的一半)，同時舍棄序列b中的前半部分(較小的一半)，要求舍棄的長度相等，如圖3.6(c)所示。在保留的兩個升序序列中重復上述過程直到兩個序列中隻含素時為止，較小者即為所求的中位數。

圖3.6求兩個等長有序序列中位數的過程

為了保證每次取的兩個子有序序列等長，對於a［s..t］，m=(s t)/2，若取前半部分，則為a［s..m］。在取後半部分時要區分素個數為奇數還是偶數，若為奇數(滿足(s t)%2==0的條件)，則後半部分為a［m..t］，若為偶數(滿足(s t)%2==1的條件)，則後半部分為a［m 1..t］。
例如，求a=(11，13，15，17，19)、b=(2，4，6，8，20)兩個有序序列的中位數的過程如圖3.7所示。

圖3.7求a、b兩個有序序列的中位數

對應的完整程序如下：

#include
void prepart(int &s,int &t)//求a［s..t］序列的前半子序列
{int m=(s t)/2;
t=m;
}
void postpart(int &s,int &t)//求a［s..t］序列的後半子序列
{int m=(s t)/2;
if ((s t)%2==0)//序列中有素
s=m;
else//序列中有素
s=m 1;
}

int midnum(int a［］,int s1,int t1,int b［］,int s2,int t2)
{//求兩個有序序列a［s1..t1］和b［s2..t2］的中位數
int m1,m2;
if (s1==t1 && s2==t2)//兩個序列隻素時返回較小者
return a［s1］else
{m1=(s1 t1)/2;//求a的中位數
m2=(s2 t2)/2;//求b的中位數
if (a［m1］==b［m2］)//兩中位數相等時返回該中位數
return a［m1］;
if (a［m1］{postpart(s1,t1);//a取後半部分
prepart(s2,t2);//b取前半部分
return midnum(a,s1,t1,b,s2,t2);
}
else//當a［m1］>b［m2］時
{prepart(s1,t1);//a取前半部分
postpart(s2,t2);//b取後半部分
return midnum(a,s1,t1,b,s2,t2);
}
}
}
void main()
{int a［］={11

商品搜索

商品分类

【醫學】

【各大出版社】