Python算法從入門到項目實踐（超值版）

劉凱燕， 副教授，河南省信息化專家、國內訪問學者、省高校計算機教育研究會高職高專分會常務委員、全國職業技能賽資格認定技能測試組專家、省計算機應用教學團隊主要負責人。主要研究方向為網絡技術、雲計算及算法應用。具備紮實的算法設計與分析能力，擅長數據結構優化、算法復雜度分析及常用機器學習算法（分類、聚類、回歸等）的工程化落地。註重將算法思想與雲計算平臺深度融合，有效提升系統性能與智能化水平。

目錄

 

第1章?Python算法入門 1

1.1　認識算法 1

1.1.1　什麼是算法 1

1.1.2　算法的特性 2

1.2　程序、編程與算法之間的關系 3

1.2.1　算法與程序 3

1.2.2　算法與編程 4

1.3　算法的表示方法 5

1.3.1　用流程圖表示算法 5

1.3.2　用N-S流程圖表示算法 6

1.3.3　用計算機語言表示算法 8

1.4　基本數據類型 8

1.4.1　列表 9

1.4.2　元組 12

1.4.3　字典 13

1.4.4　集合 16

1.5　就業面試技巧與解析 18

1.5.1　面試技巧與解析（一） 18

1.5.2　面試技巧與解析（二） 19

第2章?Python算法與數據結構 20

2.1　鏈表 20

2.1.1　單鏈表 20

2.1.2　雙鏈表 25

2.1.3　循環鏈表 30

2.1.4　鏈表的反轉 35

2.1.5　鏈表的合並 37

2.2　棧 39

2.2.1　棧的基本操作 39

2.2.2　用鏈表實現棧 41

2.2.3　用數組實現棧 43

2.3　隊列 45

2.3.1　隊列的基本操作 45

2.3.2　用鏈表實現隊列 46

2.3.3　用數組實現隊列 49

2.4　用棧實現隊列 51

2.5　用隊列實現棧 53

2.6　就業面試技巧與解析 55

2.6.1　面試技巧與解析（一） 55

2.6.2　面試技巧與解析（二） 55

第3章?查找算法 57

3.1　順序查找算法 57

3.1.1　順序查找算法的原理 57

3.1.2　順序查找算法的實現 59

3.1.3　順序查找算法的性能分析 61

3.2　折半查找算法 62

3.2.1　折半查找算法的原理 62

3.2.2　折半查找算法的實現 63

3.2.3　折半查找算法的性能分析 64

3.3　插值查找算法 65

3.3.1　插值查找算法的原理 65

3.3.2　插值查找算法的實現 66

3.3.3　插值查找算法的性能分析 68

3.4　分塊查找算法 68

3.4.1　分塊查找算法的原理 68

3.4.2　分塊查找算法的實現 70

3.4.3　分塊查找算法的性能分析 71

3.5　哈希查找算法 71

3.5.1　哈希表和哈希函數 72

3.5.2　哈希函數的構造方法 72

3.5.3　碰撞與沖突問題 75

3.5.4　哈希查找算法的實現 77

3.6　查找算法時間復雜度的比較 78

3.7　就業面試技巧與解析 79

3.7.1　面試技巧與解析（一） 79

3.7.2　面試技巧與解析（二） 80

第4章?排序算法 81

4.1　排序算法的基礎 81

4.1.1　排序的目的和過程 82

4.1.2　內部排序和外部排序 82

4.1.3　穩定排序和不穩定排序 83

4.2　選擇排序算法 83

4.2.1　選擇排序的思想 83

4.2.2　如何實現選擇排序 85

4.3　冒泡排序算法 86

4.3.1　冒泡排序的思想 86

4.3.2　如何實現冒泡排序 87

4.4　插入排序算法 89

4.4.1　插入排序的思想 89

4.4.2　如何實現插入排序 91

4.5　歸並排序算法 92

4.5.1　歸並排序的思想 92

4.5.2　如何實現歸並排序 93

4.6　希爾排序算法 95

4.6.1　希爾排序的思想 95

4.6.2　如何實現希爾排序 97

4.7　快速排序算法 98

4.7.1　快速排序的思想 98

4.7.2　如何實現快速排序 101

4.8　計數排序算法 102

4.8.1　計數排序的思想 102

4.8.2　如何實現計數排序 103

4.9　基數排序算法 104

4.9.1　基數排序的思想 104

4.9.2　如何實現基數排序 106

4.10　排序算法的比較 108

4.11　就業面試技巧與解析 108

4.11.1　面試技巧與解析（一） 108

4.11.2　面試技巧與解析（二） 109

第5章?樹與二叉樹算法 110

5.1　樹 110

5.1.1　樹的定義 110

5.1.2　樹的基本概念 111

5.2　二叉樹 112

5.2.1　二叉樹的定義與性質 112

5.2.2　二叉樹的存儲 114

5.2.3　二叉樹的遍歷 115

5.3　特殊的二叉樹結構 121

5.3.1　二叉搜索樹（BST） 121

5.3.2　平衡二叉樹（AVL樹） 126

5.4　堆與二叉堆 132

5.4.1　最大堆與最小堆 132

5.4.2　二叉堆的存儲 133

5.4.3　二叉堆的基本操作（上浮、下沈、插入、刪除） 134

5.4.4　堆排序算法 137

5.5　就業面試技巧與解析 140

5.5.1　面試技巧與解析（一） 140

5.5.2　面試技巧與解析（二） 141

第6章?遞歸與分治算法 142

6.1　遞歸算法 142

6.1.1　什麼是遞歸算法 142

6.1.2　遞歸算法的思想 143

6.2　遞歸算法的應用 144

6.2.1　計算n的階乘 144

6.2.2　斐波那契數列問題 145

6.2.3　漢諾塔問題 147

6.2.4　遞歸求全排列 149

6.2.5　N皇後問題 151

6.3　分治算法 153

6.3.1　什麼是分治算法 154

6.3.2　分治算法的思想 154

6.4　分治算法的應用 155

6.4.1　查找序列中的最大值與最小值 155

6.4.2　計算矩陣的乘積 158

6.4.3　解決多數元素問題 160

6.5　就業面試技巧與解析 161

6.5.1　面試技巧與解析（一） 161

6.5.2　面試技巧與解析（二） 162

第7章?貪心算法 163

7.1　什麼是貪心算法 163

7.2　貪心算法的思想 164

7.3　貪心算法經典應用 165

7.3.1　汽車加油問題 165

7.3.2　貨幣選擇問題 166

7.3.3　活動安排問題 167

7.3.4　最大子序和問題 168

7.3.5　背包問題 169

7.4　最小生成樹問題 172

7.4.1　認識圖 172

7.4.2　Kruskal算法 174

7.4.3　Prim算法 177

7.5　哈夫曼樹問題 179

7.6　就業面試技巧與解析 183

7.6.1　面試技巧與解析（一） 183

7.6.2　面試技巧與解析（二） 184

第8章?動態規劃算法 185

8.1　動態規劃的基本思想 185

8.2　線性動態規劃 187

8.2.1　最長遞增子序列 187

8.2.2　最長公共子序列 189

8.2.3　編輯距離問題 191

8.3　區域動態規劃 192

8.3.1　石子合並問題 193

8.3.2　矩陣鏈乘法 195

8.4　樹形動態規劃 197

8.4.1　最大路徑和問題 197

8.4.2　樹中距離之和問題 198

8.4.3　最大獨立集問題 201

8.5　背包動態規劃 203

8.5.1　0-1背包問題 203

8.5.2　完全背包問題 204

8.6　就業面試技巧與解析 206

8.6.1　面試技巧與解析（一） 206

8.6.2　面試技巧與解析（二） 207

第9章?使用Python算法解決經典問題 209

9.1　最大公約數 209

9.1.1　問題描述 210

9.1.2　算法分析 210

9.1.3　算法實現 210

9.2　尋找水仙花數 211

9.2.1　問題描述 211

9.2.2　算法分析 211

9.2.3　算法實現 211

9.3　雞兔同籠問題 212

9.3.1　問題描述 212

9.3.2　算法分析 212

9.3.3　算法實現 213

9.4　猴子分桃問題 214

9.4.1　問題描述 214

9.4.2　算法分析 214

9.4.3　算法實現 214

9.5　愛因斯坦階梯問題 215

9.5.1　問題描述 215

9.5.2　算法分析 215

9.5.3　算法實現 215

9.6　多進程驗證哥德巴赫猜想 217

9.6.1　問題描述 217

9.6.2　算法分析 217

9.6.3　算法實現 218

9.7　黃金礦工問題 220

9.7.1　問題描述 220

9.7.2　算法分析 220

9.7.3　算法實現 221

9.8　凱撒密碼問題 222

9.8.1　問題描述 222

9.8.2　算法分析 222

9.8.3　算法實現 223

9.9　約瑟夫環問題 224

9.9.1　問題描述 224

9.9.2　算法分析 224

9.9.3　算法實現 225

9.10　股票交易問題 228

9.10.1　問題描述 228

9.10.2　算法分析 228

9.10.3　算法實現 231

9.10.4　問題的變形 231