《初等算法-刘新宇》pdf

【实例截图】

【核心代码】

⽬ 录
I 前⾔ 11
0.1 算法有⽤么？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
0.2 最⼩可⽤ID，算法的威⼒ . . . . . . . . . . . . . . . . . . . . . . . . 13
0.2.1 改进⼀ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
0.2.2 改进⼆、分⽽治之 . . . . . . . . . . . . . . . . . . . . . . . . 15
0.2.3 简洁与性能――鱼和熊掌 . . . . . . . . . . . . . . . . . . . 16
0.3 丑数――数据结构的威⼒ . . . . . . . . . . . . . . . . . . . . . . . . 17
0.3.1 暴⼒解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
0.3.2 改进⼀、构造性解法 . . . . . . . . . . . . . . . . . . . . . . 18
0.3.3 改进⼆、使⽤多个队列 . . . . . . . . . . . . . . . . . . . . . 20
0.4 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
0.5 内容组织 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
II 树 25
1 ⼆叉搜索树，数据结构中的‘hello world’ 27
1.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2 数据组织 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4 遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.5 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.5.1 lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.5.2 最⼩元素和最⼤元素 . . . . . . . . . . . . . . . . . . . . . . 35
1.5.3 前驱（Successor）和后继（predecessor） . . . . . . . . . . 35
1.6 删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.7 随机构建⼆叉搜索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2 插⼊排序的进化 43
2.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 改进⼀，⼆分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 改进⼆，使⽤链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5 使⽤⼆叉搜索树的最终改进 . . . . . . . . . . . . . . . . . . . . . . . 49
2.6 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3
4 ⽬ 录
3 并不复杂的红⿊树 51
3.0.1 如何保证树的平衡 . . . . . . . . . . . . . . . . . . . . . . . . 52
3.0.2 树的旋转 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1 红⿊树的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4 命令式的红⿊树算法⋆ . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5 其它 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 AVL树 71
4.1 AVL树的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2.1 平衡调整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2.1.1 左－左偏（Left-left lean）的情况 . . . . . . . . . 77
4.2.1.2 右－右偏（Right-right lean）的情况 . . . . . . . . 77
4.2.1.3 右－左偏（Right-left lean）的情况 . . . . . . . . 77
4.2.1.4 左－右偏（Left-right lean）的情况 . . . . . . . . 79
4.2.2 模式匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.2.1 验证 . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3 删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4 AVL树的命令式算法⋆ . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5 基数树－Trie和Patricia 85
5.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 整数Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 整数Trie的定义 . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2.3 查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3 整数Patricia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.3.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.3 查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4 字符Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.4.3 查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5 字符Patricia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5.3 查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.6 Trie和Patricia的应⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6.1 电⼦词典和单词⾃动补齐 . . . . . . . . . . . . . . . . . . . 108
5.6.2 T9输⼊法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.7 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
⽬ 录 5
6 后缀树 119
6.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2 后缀Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.2.1 节点转移和后缀链接 . . . . . . . . . . . . . . . . . . . . . . 120
6.2.2 On-line构造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.3 后缀树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.3.1 on-line构造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.3.1.1 活动点（active point）和终⽌点（end point） . . 126
6.3.1.2 引⽤对（Reference pair） . . . . . . . . . . . . . . 127
6.3.1.3 归⼀化引⽤对 . . . . . . . . . . . . . . . . . . . . . 127
6.3.1.4 Ukkonen算法 . . . . . . . . . . . . . . . . . . . . . 128
6.3.1.5 函数式构造后缀树 . . . . . . . . . . . . . . . . . . 133
6.4 后缀树的应⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4.1 字符串搜索和模式匹配 . . . . . . . . . . . . . . . . . . . . . 135
6.4.1.1 ⼦串出现的次数 . . . . . . . . . . . . . . . . . . . 135
6.4.2 查找最长重复⼦串 . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.3 查找最长公共⼦串 . . . . . . . . . . . . . . . . . . . . . . . . 138
6.4.4 查找最长回⽂ . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.4.5 其它 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7 B树 141
7.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.2.1 分拆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.2.1.1 插⼊前预分拆 . . . . . . . . . . . . . . . . . . . . . 144
7.2.1.2 先插⼊再修复 . . . . . . . . . . . . . . . . . . . . . 147
7.3 删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.3.1 删除前预合并 . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.3.2 先删除再修复 . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.4 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
III 堆 165
8 ⼆叉堆 167
8.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2 ⽤数组实现隐式⼆叉堆 . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2.2 Heapify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.2.3 构造堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.2.4 堆的基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.2.4.1 获取顶部元素 . . . . . . . . . . . . . . . . . . . . . 171
8.2.4.2 弹出堆顶元素 . . . . . . . . . . . . . . . . . . . . . 173
8.2.4.3 寻找top k个元素 . . . . . . . . . . . . . . . . . . . 173
8.2.4.4 减⼩key值 . . . . . . . . . . . . . . . . . . . . . . . 174
8.2.4.5 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.2.5 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.3 左偏堆和skew堆―显式的⼆叉堆 . . . . . . . . . . . . . . . . . . . . 177
6 ⽬ 录
8.3.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.3.1.1 Rank（S-值） . . . . . . . . . . . . . . . . . . . . . 178
8.3.1.2 左偏性质 . . . . . . . . . . . . . . . . . . . . . . . 178
8.3.2 合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
8.3.2.1 合并由数组表⽰的⼆叉堆 . . . . . . . . . . . . . . 179
8.3.3 基本堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.3.3.1 获取顶部元素和弹出操作 . . . . . . . . . . . . . . 180
8.3.3.2 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.3.4 使⽤左偏堆实现堆排序 . . . . . . . . . . . . . . . . . . . . . 181
8.3.5 Skew堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.3.5.1 Skew堆的定义 . . . . . . . . . . . . . . . . . . . . . 181
8.3.5.2 合并 . . . . . . . . . . . . . . . . . . . . . . . . . . 182
8.4 伸展堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8.4.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8.4.1.1 伸展操作 . . . . . . . . . . . . . . . . . . . . . . . 183
8.4.1.2 获取和弹出顶部元素 . . . . . . . . . . . . . . . . . 188
8.4.1.3 合并 . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.4.2 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9 从吃葡萄到世界杯，选择排序的进化 191
9.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 查找最⼩元素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
9.2.1 标记 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
9.2.2 分组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
9.2.3 选择排序的性能 . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.3 细微改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.3.1 ⽐较⽅法参数化 . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.3.2 细微调整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
9.3.3 鸡尾酒排序（Cock-tail sort） . . . . . . . . . . . . . . . . . 198
9.4 本质改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
9.4.1 锦标赛淘汰法 . . . . . . . . . . . . . . . . . . . . . . . . . . 201
9.4.1.1 锦标赛淘汰法的细节改进 . . . . . . . . . . . . . . 206
9.4.2 使⽤堆排序进⾏最后的改进 . . . . . . . . . . . . . . . . . . 208
9.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10 ⼆项式堆，斐波那契堆和配对堆 211
10.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.2 ⼆项式堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.2.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.2.1.1 ⼆项式树 . . . . . . . . . . . . . . . . . . . . . . . 211
10.2.1.2 ⼆项式堆 . . . . . . . . . . . . . . . . . . . . . . . 212
10.2.1.3 数据布局 . . . . . . . . . . . . . . . . . . . . . . . 214
10.2.2 基本的堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . 215
10.2.2.1 树的链接 . . . . . . . . . . . . . . . . . . . . . . . 215
10.2.2.2 插⼊新元素（push） . . . . . . . . . . . . . . . . . 217
10.2.2.3 堆合并 . . . . . . . . . . . . . . . . . . . . . . . . . 219
10.2.2.4 弹出 . . . . . . . . . . . . . . . . . . . . . . . . . . 222
10.2.2.5 其他 . . . . . . . . . . . . . . . . . . . . . . . . . . 224
10.3 斐波那契堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
⽬ 录 7
10.3.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
10.3.2 基本堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.3.2.1 插⼊新元素 . . . . . . . . . . . . . . . . . . . . . . 226
10.3.2.2 堆合并 . . . . . . . . . . . . . . . . . . . . . . . . . 227
10.3.2.3 弹出（删除最⼩元素） . . . . . . . . . . . . . . . 228
10.3.3 弹出操作的性能分析 . . . . . . . . . . . . . . . . . . . . . . 232
10.3.4 减⼩key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10.3.5 斐波那契堆名字的由来 . . . . . . . . . . . . . . . . . . . . . 237
10.4 配对堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.4.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.4.2 基本堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
10.4.2.1 合并、插⼊、和获取顶部元素 . . . . . . . . . . . 240
10.4.2.2 减⼩节点的值 . . . . . . . . . . . . . . . . . . . . . 241
10.4.2.3 弹出 . . . . . . . . . . . . . . . . . . . . . . . . . . 242
10.4.2.4 删除节点 . . . . . . . . . . . . . . . . . . . . . . . 245
10.5 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
IV 队列和序列 247
11 并不简单的队列 249
11.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
11.2 单向列表和循环缓冲区实现的队列 . . . . . . . . . . . . . . . . . . 249
11.2.1 单向链表实现 . . . . . . . . . . . . . . . . . . . . . . . . . . 249
11.2.2 循环缓冲区实现 . . . . . . . . . . . . . . . . . . . . . . . . . 251
11.3 纯函数式实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
11.3.1 双列表队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
11.3.2 双数组队列——⼀种对称实现 . . . . . . . . . . . . . . . . . 257
11.4 ⼩改进：平衡队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.5 进⼀步改进：实时队列 . . . . . . . . . . . . . . . . . . . . . . . . . 260
11.5.0.1 逐步反转 . . . . . . . . . . . . . . . . . . . . . . . 261
11.5.0.2 逐步连接 . . . . . . . . . . . . . . . . . . . . . . . 262
11.5.0.3 汇总 . . . . . . . . . . . . . . . . . . . . . . . . . . 263
11.6 惰性实时队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
11.7 ⼩节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
12 序列，最后⼀块砖 271
12.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
12.2 ⼆叉随机访问列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
12.2.1 普通数组和列表 . . . . . . . . . . . . . . . . . . . . . . . . . 272
12.2.2 使⽤森林表⽰序列 . . . . . . . . . . . . . . . . . . . . . . . . 272
12.2.3 在序列的头部插⼊ . . . . . . . . . . . . . . . . . . . . . . . . 273
12.2.3.1 从序列头部删除元素 . . . . . . . . . . . . . . . . . 275
12.2.3.2 随机访问元素 . . . . . . . . . . . . . . . . . . . . . 276
12.3 ⼆叉随机访问列表的数字表⽰（Numeric representation） . . . . . 279
12.3.1 命令式⼆叉随机访问列表 . . . . . . . . . . . . . . . . . . . 281
12.4 命令式双数组列表（paired-array list） . . . . . . . . . . . . . . . . 284
12.4.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
12.4.2 插⼊和添加 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
12.4.3 随机访问 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8 ⽬ 录
12.4.4 删除和平衡 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
12.5 可连接列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
12.6 ⼿指树（Finger Tree） . . . . . . . . . . . . . . . . . . . . . . . . . . 290
12.6.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
12.6.2 向序列的头部插⼊元素 . . . . . . . . . . . . . . . . . . . . . 293
12.6.3 从头部删除元素 . . . . . . . . . . . . . . . . . . . . . . . . . 295
12.6.4 删除时处理不规则的⼿指树 . . . . . . . . . . . . . . . . . . 296
12.6.5 在序列的尾部添加元素 . . . . . . . . . . . . . . . . . . . . . 301
12.6.6 从尾部删除元素 . . . . . . . . . . . . . . . . . . . . . . . . . 302
12.6.7 连接 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
12.6.8 ⼿指树的随机访问 . . . . . . . . . . . . . . . . . . . . . . . . 308
12.6.8.1 增加size记录 . . . . . . . . . . . . . . . . . . . . . 308
12.6.8.2 增加size信息后引⼊的改动 . . . . . . . . . . . . . 310
12.6.8.3 在指定位置分割⼿指树 . . . . . . . . . . . . . . . 312
12.6.8.4 随机访问 . . . . . . . . . . . . . . . . . . . . . . . 313
12.6.8.5 命令式随机访问 . . . . . . . . . . . . . . . . . . . 314
12.6.8.6 命令式分割 . . . . . . . . . . . . . . . . . . . . . . 316
12.7 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
V 排序和搜索 321
13 分⽽治之，快速排序和归并排序 323
13.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
13.2 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
13.2.1 基本形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
13.2.2 严格弱序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
13.2.3 划分（partition） . . . . . . . . . . . . . . . . . . . . . . . . 325
13.2.4 函数式划分算法的⼩改进 . . . . . . . . . . . . . . . . . . . 328
13.2.4.1 累积划分（Accumulated partition） . . . . . . . . 329
13.2.4.2 累积式快速排序 . . . . . . . . . . . . . . . . . . . 329
13.3 快速排序的性能分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
13.3.1 平均情况的分析 ⋆ . . . . . . . . . . . . . . . . . . . . . . . . 331
13.4 ⼯程实践中的改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
13.4.1 处理重复元素的⼯程⽅法 . . . . . . . . . . . . . . . . . . . 334
13.4.1.1 双向划分（2-way partition） . . . . . . . . . . . . 335
13.4.1.2 三路划分 . . . . . . . . . . . . . . . . . . . . . . . 337
13.5 针对最差情况的⼯程实践 . . . . . . . . . . . . . . . . . . . . . . . . 340
13.6 其他⼯程实践 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
13.7 其他 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
13.8 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
13.8.1 基本归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . 345
13.8.1.1 归并 . . . . . . . . . . . . . . . . . . . . . . . . . . 345
13.8.1.2 性能 . . . . . . . . . . . . . . . . . . . . . . . . . . 348
13.8.1.3 细微改进 . . . . . . . . . . . . . . . . . . . . . . . 348
13.9 原地归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
13.9.1 死板的原地归并 . . . . . . . . . . . . . . . . . . . . . . . . . 352
13.9.2 原地⼯作区 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
13.9.3 原地归并排序vs.链表归并排序 . . . . . . . . . . . . . . . . . 357
13.10 ⾃然归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
⽬ 录 9
13.11 ⾃底向上归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
13.12 并⾏处理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
13.13 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
14 搜索 369
14.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.2 序列搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.2.1 分⽽治之的搜索 . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.2.1.1 k选择问题 . . . . . . . . . . . . . . . . . . . . . . . 369
14.2.1.2 ⼆分查找 . . . . . . . . . . . . . . . . . . . . . . . 373
14.2.1.3 ⼆维搜索 . . . . . . . . . . . . . . . . . . . . . . . 376
14.2.1.3.1 穷举法⼆维搜索 . . . . . . . . . . . . . . 377
14.2.1.3.2 Saddleback搜索 . . . . . . . . . . . . . . 377
14.2.1.3.3 改进的saddleback搜索 . . . . . . . . . . 380
14.2.1.3.4 Saddleback搜索的进⼀步改进 . . . . . . 382
14.2.2 信息复⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
14.2.2.1 Boyer-Moore众数问题 . . . . . . . . . . . . . . . . 388
14.2.2.2 最⼤⼦序列和 . . . . . . . . . . . . . . . . . . . . . 392
14.2.2.3 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . 393
14.2.2.3.1 纯函数式KMP算法 . . . . . . . . . . . . 397
14.2.2.4 Boyer-Moore字符串匹配算法 . . . . . . . . . . . . 404
14.2.2.4.1 不良字符（bad-character）启发条件 . . 405
14.2.2.4.2 良好后缀启发条件 . . . . . . . . . . . . . 407
14.3 解的搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
14.3.1 深度优先搜索（DFS）和⼴度优先搜索（BFS） . . . . . . 413
14.3.1.1 迷宫 . . . . . . . . . . . . . . . . . . . . . . . . . . 413
14.3.1.2 ⼋皇后问题 . . . . . . . . . . . . . . . . . . . . . . 418
14.3.1.3 跳棋趣题 . . . . . . . . . . . . . . . . . . . . . . . 421
14.3.1.4 深度优先搜索的⼩结 . . . . . . . . . . . . . . . . . 425
14.3.1.5 狼、⽺、⽩菜趣题 . . . . . . . . . . . . . . . . . . 426
14.3.1.6 倒⽔问题 . . . . . . . . . . . . . . . . . . . . . . . 431
14.3.1.7 华容道 . . . . . . . . . . . . . . . . . . . . . . . . . 439
14.3.1.8 ⼴度优先搜索的⼩结 . . . . . . . . . . . . . . . . . 445
14.3.2 搜索最优解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
14.3.2.1 贪⼼算法 . . . . . . . . . . . . . . . . . . . . . . . 447
14.3.2.1.1 Huffman编码 . . . . . . . . . . . . . . . . 447
14.3.2.1.2 换零钱问题 . . . . . . . . . . . . . . . . . 456
14.3.2.1.3 贪⼼⽅法的⼩结 . . . . . . . . . . . . . . 457
14.3.2.2 动态规划 . . . . . . . . . . . . . . . . . . . . . . . 458
14.3.2.2.1 动态规划的性质 . . . . . . . . . . . . . . 463
14.3.2.2.2 最长公共⼦序列问题 . . . . . . . . . . . 463
14.3.2.2.3 ⼦集和问题 . . . . . . . . . . . . . . . . . 467
14.4 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
VI 附录 475
Appendices
10 ⽬ 录
A 列表 477
A.1 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
A.2 列表的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
A.2.1 空列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
A.2.2 获取元素和⼦列表 . . . . . . . . . . . . . . . . . . . . . . . . 478
A.3 列表的基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
A.3.1 构建 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
A.3.2 判空和长度计算 . . . . . . . . . . . . . . . . . . . . . . . . . 479
A.3.3 索引 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
A.3.4 获取最后的元素 . . . . . . . . . . . . . . . . . . . . . . . . . 481
A.3.5 反向索引 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
A.3.6 修改 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
A.3.6.1 添加（Append） . . . . . . . . . . . . . . . . . . . 485
A.3.6.2 修改指定位置上的元素 . . . . . . . . . . . . . . . 486
A.3.6.3 插⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . 487
A.3.6.4 删除 . . . . . . . . . . . . . . . . . . . . . . . . . . 490
A.3.6.5 连接 . . . . . . . . . . . . . . . . . . . . . . . . . . 492
A.3.7 和与积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
A.3.7.1 递归求和与求积 . . . . . . . . . . . . . . . . . . . 493
A.3.7.2 尾递归 . . . . . . . . . . . . . . . . . . . . . . . . . 494
A.3.7.3 命令式的求和与求积 . . . . . . . . . . . . . . . . . 497
A.3.8 最⼤值和最⼩值 . . . . . . . . . . . . . . . . . . . . . . . . . 497
A.4 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
A.4.1 映射（map）和for-each . . . . . . . . . . . . . . . . . . . . . 500
A.4.1.1 映射 . . . . . . . . . . . . . . . . . . . . . . . . . . 501
A.4.1.2 For each . . . . . . . . . . . . . . . . . . . . . . . . 503
A.4.1.3 映射的例⼦ . . . . . . . . . . . . . . . . . . . . . . 504
A.4.2 反转 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
A.5 提取⼦列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
A.5.1 截取（take）、丢弃（drop）、和分割（split-at） . . . . . 508
A.5.1.1 take-while和drop-while . . . . . . . . . . . . . . . . 509
A.5.1.2 split-at . . . . . . . . . . . . . . . . . . . . . . . . . 509
A.5.2 切分和分组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
A.5.2.1 切分 . . . . . . . . . . . . . . . . . . . . . . . . . . 509
A.5.2.2 分组 . . . . . . . . . . . . . . . . . . . . . . . . . . 510
A.6 Fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
A.6.1 从右侧fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
A.6.2 从左侧fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
A.6.2.1 命令式fold和抽象fold概念 . . . . . . . . . . . . . 517
A.6.3 fold的应⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
A.6.3.1 连接列表的列表 . . . . . . . . . . . . . . . . . . . 519
A.7 搜索和匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
A.7.1 存在检查 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
A.7.2 lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
A.7.3 ﾞnd和ﾞlter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
A.7.4 匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
A.8 zip和unzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
A.9 ⼩结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527