秒懂算法：用常识解读数据结构与算法

适读人群 ：本书适合初级和中级程序员阅读，不局限于某一种编程语言。

* 面对时间复杂度相同的两个算法，如何判断哪个更好？

* 如何快速分析出某段代码的效率？

* 要写出优雅的代码，有哪些窍门？

翻开本书，秒懂算法，体验顿悟瞬间。

帮助你学习算法思维，以及如何使用并实现一系列常见数据结构。全书语言清晰简洁，行文诙谐生动，尽可能少地使用专业术语。

本书是简单易懂的数据结构与算法入门书。作者略过复杂的数学公式，用“通俗讲解×逐步图示×代码实现”的方式介绍了数据结构与算法的基本概念，培养读者的算法思维。全书共有20章。读者将了解数据结构与算法为何如此重要，如何快速使用大O记法判断代码的运行效率，以及如何用动态规划优化算法。本书的重点内容包括冒泡排序、选择排序、插入排序等排序算法，以及深度优先搜索、广度优先搜索、迪杰斯特拉算法等图算法。在学习算法的过程中，读者也将通晓数组、哈希表、栈、队列、链表、图等常用数据结构的适用场景。

【作者简介】

杰伊·温格罗（Jay Wengrow）

经验丰富的讲师、软件工程师，一直致力于全民编程教育，编程培训公司Actualize和Anyone Can Learn to Code的创始人兼CEO。

【译者简介】

姜喆

普渡大学计算机科学硕士，具备扎实的数据结构与算法基础，熟悉C、JavaScript、Java和Python。曾在互联网行业和金融行业从事软件开发工作，现就职于游戏公司。另译有《不可能的几何挑战：数学求索两千年》。

第 1 章 数据结构为何重要 1
1．1 数据结构 2
1．2 数组：基础数据结构 3
1．3 速度计量 4
1．4 读取 4
1．5 查找 7
1．6 插入 9
1．7 删除 11
1．8 集合：差之毫厘，“慢”之千里 12
1．9 小结 15
习题 15
第 2 章 算法为何重要 17
2．1 有序数组 18
2．2 有序数组的查找 20
2．3 二分查找 21
2．4 二分查找与线性查找 25
2．5 小结 27
习题 28
第 3 章 哦！大O记法 29
3．1 大O：对N个元素来说需要多少步 29
3．2 大O的灵魂 30
3．2．1 深入大O的灵魂 32
3．2．2 同样的算法，不同的场景 32
3．3 第三类算法 33
3．4 对数 34
3．5 O(log N)的含义 34
3．6 实际例子 35
3．7 小结 36
习题 36
第 4 章 使用大O给代码提速 38
4．1 冒泡排序 38
4．2 冒泡排序实战 39
4．3 冒泡排序的效率 44
4．4 平方问题 45
4．5 线性解法 47
4．6 小结 48
习题 49
第 5 章 用或不用大O来优化代码 50
5．1 选择排序 50
5．2 选择排序实战 51
5．3 选择排序的效率 55
5．4 忽略常数 56
5．5 大O类别 57
5．5．1 实际例子 58
5．5．2 关键步骤 59
5．6 小结 59
习题 60
第 6 章 根据情况进行优化 61
6．1 插入排序 61
6．2 插入排序实战 62
6．3 插入排序的效率 67
6．4 平均情况 68
6．5 实际例子 70
6．6 小结 72
习题 72
第 7 章 日常代码中的大O 74
7．1 偶数平均数 74
7．2 构词程序 75
7．3 数组抽样 77
7．4 摄氏温度平均值 78
7．5 衣服标签 79
7．6 1的个数 80
7．7 回文检查 80
7．8 计算所有的积 81
7．9 密码破解程序 84
7．10 小结 86
习题 86
第 8 章 查找迅速的哈希表 89
8．1 哈希表 89
8．2 用哈希函数进行哈希 90
8．3 好玩又赚钱的同义词典（赚钱是重点） 91
8．4 哈希表查找 92
8．5 解决冲突 94
8．6 创造高效的哈希表 96
8．7 用哈希表整合数据 98
8．8 用哈希表优化速度 99
8．9 小结 103
习题 103
第 9 章 用栈和队列打造优雅的代码 104
9．1 栈 104
9．2 抽象数据类型 106
9．3 栈实战 107
9．4 受限数据结构的重要性 112
9．5 队列 113
9．6 队列实战 114
9．7 小结 116
习题 116
第 10 章 用递归不停递归 117
10．1 用递归代替循环 117
10．2 基准情形 118
10．3 阅读递归代码 119
10．4 计算机眼中的递归 121
10．4．1 调用栈 121
10．4．2 栈溢出 123
10．5 文件系统遍历 123
10．6 小结 125
习题 125
第 11 章 学习编写递归代码 127
11．1 递归类别：重复执行 127
11．2 递归类别：计算 130
11．3 自上而下递归：新的思维方式 132
11．3．1 自上而下的思考过程 133
11．3．2 数组的和 133
11．3．3 字符串倒序 134
11．3．4 x的个数 135
11．4 台阶问题 136
11．5 易位构词生成 139
11．6 小结 142
习题 143
第 12 章 动态规划 144
12．1 不必要的递归调用 144
12．2 大O小改 147
12．3 递归的效率 148
12．4 重复子问题 149
12．5 动态规划与记忆化 150
12．6 自下而上的动态规划 153
12．6．1 自下而上的斐波那契函数 154
12．6．2 记忆化与自下而上 154
12．7 小结 155
习题 155
第 13 章 飞快的递归算法 156
13．1 分区 156
13．2 快速排序 161
13．3 快速排序的效率 165
13．3．1 快速排序鸟瞰 166
13．3．2 快速排序的时间复杂度 167
13．4 最坏情况下的快速排序 169
13．5 快速选择 171
13．5．1 快速选择的效率 172
13．5．2 代码实现：快速选择 173
13．6 基于排序的其他算法 173
13．7 小结 175
习题 175
第 14 章 基于节点的数据结构 176
14．1 链表 176
14．2 链表实现 177
14．3 读取 179
14．4 查找 180
14．5 插入 181
14．6 删除 185
14．7 链表操作的效率 187
14．8 链表实战 187
14．9 双链表 188
14．9．1 代码实现：双链表插入 189
14．9．2 前后移动 190
14．10 队列的双链表实现 190
14．11 小结 192
习题 192
第 15 章 用二叉查找树加速万物 193
15．1 树 193
15．2 二叉查找树 195
15．3 查找 196
15．3．1 二叉查找树的查找效率 198
15．3．2 logN层 198
15．3．3 代码实现：二叉查找树查找 199
15．4 插入 200
15．4．1 代码实现：二叉查找树插入 202
15．4．2 插入顺序 203
15．5 删除 203
15．5．1 删除有两个子节点的节点 204
15．5．2 找到后继节点 205
15．5．3 有右子节点的后继节点 206
15．5．4 完整的删除算法 208
15．5．5 代码实现：二叉查找树删除 208
15．5．6 二叉查找树删除的效率 211
15．6 二叉查找树实战 211
15．7 二叉查找树遍历 212
15．8 小结 215
习题 216
第 16 章 使用堆分清主次 217
16．1 优先队列 217
16．2 堆 218
16．2．1 堆条件 219
16．2．2 完全树 220
16．3 堆的性质 221
16．4 堆的插入 222
16．5 寻找尾节点 223
16．6 堆的删除 224
16．7 堆和有序数组 227
16．8 重新解决尾节点问题 228
16．9 用数组实现堆 230
16．9．1 遍历基于数组的堆 231
16．9．2 代码实现：堆插入 232
16．9．3 代码实现：堆删除 233
16．9．4 堆的其他实现方法 235
16．10 用堆实现优先队列 235
16．11 小结 236
习题 236
第 17 章 字典树又何妨 237
17．1 字典树 237
17．1．1 字典树节点 238
17．1．2 Trie类 238
17．2 存储单词 239
17．3 字典树查找 241
17．4 字典树查找的效率 245
17．5 字典树插入 246
17．6 实现自动补全 249
17．6．1 收集所有单词 249
17．6．2 递归过程分析 251
17．7 完成自动补全功能 254
17．8 带有值的字典树：更好的自动补全 255
17．9 小结 256
习题 257
第 18 章 连接万物的图 258
18．1 图 258
18．1．1 图和树 259
18．1．2 图的术语 259
18．1．3 图的基本实现 260
18．2 有向图 260
18．3 面向对象的图实现 261
18．4 图的搜索 262
18．5 深度优先搜索 264
18．5．1 深度优先搜索步骤详解 265
18．5．2 代码实现：深度优先搜索 271
18．6 广度优先搜索 272
18．6．1 广度优先搜索步骤详解 273
18．6．2 代码实现：广度优先搜索 280
18．6．3 对比广度优先搜索与深度优先搜索 281
18．7 图的搜索效率 283
18．8 加权图 285
18．8．1 加权图的代码实现 286
18．8．2 最短路径问题 287
18．9 迪杰斯特拉算法 288
18．9．1 迪杰斯特拉算法的准备工作 288
18．9．2 迪杰斯特拉算法的步骤 289
18．9．3 迪杰斯特拉算法详解 289
18．9．4 找到最短路径 295
18．9．5 代码实现：迪杰斯特拉算法 296
18．9．6 迪杰斯特拉算法的效率 301
18．10 小结 301
习题 302
第 19 章 对付空间限制 304
19．1 空间复杂度的大O记法 304
19．2 时间和空间的取舍 306
19．3 递归的隐藏成本 308
19．4 小结 310
习题 310
第 20 章 代码优化技巧 312
20．1 前置工作：确定目前的时间复杂度 312
20．2 从这里开始：最理想复杂度 312
20．3 魔法查找 313
20．3．1 魔法查找：查找作者 314
20．3．2 使用其他数据结构 315
20．3．3 两数之和问题 317
20．4 找规律 319
20．4．1 硬币游戏 319
20．4．2 举例法 320
20．4．3 交换和问题 321
20．5 贪心算法 325
20．5．1 数组最大值 326
20．5．2 最大子数组和 326
20．5．3 贪心的股价预测 331
20．6 更换数据结构 335
20．6．1 易位构词检查器 335
20．6．2 分组排序 338
20．7 小结 340
20．8 临别感言 340
习题 341
附录 习题答案（图灵社区下载）