描述
开 本: 128开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787115440358
伪代码与多语言实现并存，充分发挥语言特性
理论与实例结合，轻松学习算法与数据结构
内含ACM竞赛趣题和传统趣题，发现算法的乐趣
七年磨一剑，亚马逊中国高级研发人员重磅力作
部分 树
第1章 二叉搜索树：数据结构中的“hello world” 3
1.1 定义 3
1.2 数据组织 5
1.3 插入 6
1.4 遍历 8
1.5 搜索 10
1.5.1 lookup 10
1.5.2 小元素和元素 11
1.5.3 前驱和后继 12
1.6 删除 14
1.7 随机构建二叉搜索树 18
第2章 插入排序的进化 19
2.1 简介 19
2.2 插入 20
2.3 改进一：二分查找 20
2.4 改进二：使用链表 22
2.5 使用二叉搜索树的终改进 26
2.6 小结 27
第3章 并不复杂的红黑树 28
3.1 红黑树的定义 32
3.2 插入 33
3.3 删除 36
3.4 命令式的红黑树算法?* 44
3.5 小结 47
第4章 AVL树 48
4.1 AVL树的定义 48
4.2 插入 51
4.2.1 平衡调整 53
4.2.2 模式匹配 57
4.3 删除 59
4.4 AVL树的命令式算法?* 59
4.5 小结 63
第5章 基数树：Trie和Patricia 65
5.1 整数Trie 65
5.1.1 整数Trie的定义 67
5.1.2 插入 67
5.1.3 查找 69
5.2 整数Patricia 70
5.2.1 定义 71
5.2.2 插入 72
5.2.3 查找 78
5.3 字符Trie 80
5.3.1 定义 80
5.3.2 插入 81
5.3.3 查找 83
5.4 字符Patricia 84
5.4.1 定义 84
5.4.2 插入 85
5.4.3 查找 90
5.5 Trie和Patricia的应用 92
5.5.1 电子词典和单词自动补齐 92
5.5.2 T9输入法 97
5.6 小结 102
第6章 后缀树 103
6.1 后缀Trie 104
6.1.1 节点转移和后缀链接 105
6.1.2 on-line构造 107
6.2 后缀树 111
6.3 后缀树的应用 121
6.3.1 字符串搜索和模式匹配 121
6.3.2 查找长重复子串 123
6.3.3 查找长公共子串 125
6.3.4 查找长回文 127
6.3.5 其他 128
6.4 小结 128
第7章 B树 129
7.1 插入 131
7.2 删除 139
7.2.1 删除前预合并 139
7.2.2 先删除再修复 139
7.3 搜索 153
7.4 小结 155
第二部分
堆
第8章 二叉堆 159
8.1 用数组实现隐式二叉堆 159
8.1.1 定义 159
8.1.2 Heapify 160
8.1.3 构造堆 163
8.1.4 堆的基本操作 164
8.1.5 堆排序 168
8.2 左偏堆和skew堆:显式的二叉堆 169
8.2.1 定义 170
8.2.2 合并 172
8.2.3 基本堆操作 173
8.2.4 使用左偏堆实现堆排序 174
8.2.5 skew堆 174
8.3 伸展堆 177
8.3.1 定义 177
8.3.2 堆排序 183
8.4 小结 183
第9章 从吃葡萄到世界杯：选择排序的进化 184
9.1 查找小元素 186
9.1.1 标记 186
9.1.2 分组 188
9.1.3 选择排序的性能 189
9.2 细微改进 190
9.2.1 比较方法参数化 190
9.2.2 细微调整 191
9.2.3 鸡尾酒排序 192
9.3 本质改进 196
9.3.1 锦标赛淘汰法 196
9.3.2 使用堆排序进行后的改进 204
9.4 小结 204
第10章 二项式堆、斐波那契堆和配对堆 205
10.1 二项式堆 205
10.1.1 定义 205
10.1.2 基本的堆操作 209
10.2 斐波那契堆 220
10.2.1 定义 220
10.2.2 基本堆操作 221
10.2.3 弹出操作的性能分析 230
10.2.4 减小key 232
10.2.5 “斐波那契堆”名字的由来 234
10.3 配对堆 237
10.3.1 定义 237
10.3.2 基本堆操作 238
10.4 小结 244
第三部分
队列和序列
第11章 并不简单的队列 247
11.1 单向链表和循环缓冲区实现的队列 247
11.1.1 单向链表实现 247
11.1.2 循环缓冲区实现 251
11.2 纯函数式实现 253
11.2.1 双列表队列 254
11.2.2 双数组队列：一种对称实现 255
11.3 小改进：平衡队列 257
11.4 进一步改进：实时队列 259
11.5 惰性实时队列 266
11.6 小结 269
第12章 序列：后一块砖 271
12.1 二叉随机访问列表 271
12.1.1 普通数组和列表 271
12.1.2 使用森林表示序列 272
12.1.3 在序列的头部插入 273
12.2 二叉随机访问列表的数值表示 279
12.3 命令式双数组列表 285
12.3.1 定义 285
12.3.2 插入和添加 286
12.3.3 随机访问 286
12.3.4 删除和平衡 287
12.4 可连接列表 289
12.5 手指树 293
12.5.1 定义 293
12.5.2 向序列的头部插入元素 295
12.5.3 从头部删除元素 298
12.5.4 删除时处理不规则的手指树 300
12.5.5 在序列的尾部添加元素 304
12.5.6 从尾部删除元素 306
12.5.7 连接 307
12.5.8 手指树的随机访问 312
12.6 小结 325
第四部分
排序和搜索
第13章 分而治之：快速排序和归并排序 329
13.1 快速排序 329
13.1.1 基本形式 330
13.1.2 严格弱序 331
13.1.3 划分 331
13.1.4 函数式划分算法的小改进 335
13.2 快速排序的性能分析 337
13.3 工程实践中的改进 340
13.4 针对差情况的工程实践 348
13.5 其他工程实践 351
13.6 其他 351
13.7 归并排序 352
13.8 原地归并排序 360
13.8.1 死板原地归并 360
13.8.2 原地工作区 362
13.8.3 原地归并排序与链表归并排序 366
13.9 自然归并排序 368
13.10 自底向上归并排序 374
13.11 并行处理 377
13.12 小结 377
第14章 搜索 379
14.1 序列搜索 379
14.1.1 分而治之的搜索 379
14.1.2 信息复用 400
14.2 解的搜索 428
14.2.1 深度优先搜索和广度优先搜索 428
14.2.2 搜索解 468
14.3 小结 498
附录
列表 500
列表的定义 500
列表的基本操作 502
变换 527
提取子列表 536
fold 543
搜索和匹配 549
zip和unzip 555
小结 558
参考文献 559
索引 563
我几年前曾经粗略读过这本书的英文书稿Elementary Algorithms，五六百页的一本算法书，是作者多年来在学术界和工业界实践中不断思考的结晶。那本英文书稿因为对几个算法问题的独到解读，成为英文世界中很多人学习算法的参考资料。这次我拿到新宇的中文版书稿《算法新解》，感觉内容更加充实丰富，文笔更加流畅，引文更加全面，结构更加紧凑，我也更加不读完不能释手。过去有人告诉我又一本中文版算法书要出版时，我通常的反应都是“又一本？”，并嗤之以鼻。毕竟中文的计算机算法书质量良莠不齐，而且存在大量照翻英文书的现象，而这本《算法新解》则是作者多年知识积累下的原创之作。更加难得的是，作者在书后给出了详细的参考文献，供读者进一步学习参考。
从计算机语言知识的角度看，这本书虽然原叫“初等”算法，但是对读者的要求并不低，
书中大量使用了C/C 、Python
和Haskell 这几种语言。C/C 和Python 作为传统而又实用的两种语言，包含了指令语言、面向对象和动态语言等几种形态，为从业人员和普通大众所广泛使用和熟悉。那么，为什么要用Haskell 呢？孙中山曾经说过“世界潮流，浩浩荡荡，顺之则昌，逆之则亡”，计算机语言的进化过程也一样。计算机语言从初的“让机器能理解人的交流工具”，逐渐进化到可以描述人类思考过程的更加抽象、数学上更严谨，也更加强大的函数式编程语言，而Haskell 就是函数式编程语言的代表。如果要读懂这本书的深刻精髓，你需要一点Haskell
知识；如果你之前没有学过，也让这本书成为你学习一门函数式编程语言的动力之一吧！
从算法理论的角度看，这本书深入浅出。作者先花大量篇幅讲述重要的几种数据结构和相关的处理方法，然后用大量经典而又新颖的问题来讲述计算机算法的核心问题：如何排序和搜索。这本书在前半部分介绍基本的数据结构时没有落入俗套，而是从树、堆讲起，后介绍“并不简单”的队列，让人不禁想起张筑生先生先讲积分、后讲微分的经典名著《数学分析新讲》。我很喜欢作者介绍排序算法时对“冒泡排序”的处理：本书并不花费篇幅谈论如此低效的算法，读者可到维基百科自行花5 分钟理解。相反，作者用了100 多页的篇幅，通过经典而又有趣的谜题详细讲解了各种搜索算法。更难得的是，作者大量使用函数式编程语言来做范例，展示了这类语言的强大之处，这在很多中文算法书中是看不到的。
从思考解决各种有趣问题的角度看，这本书适合任何知识背景和层次的读者“享用”。算法不仅仅可以用来解决现实世界中的种种实际问题，比如通过关键词寻找网上有用的信息，寻找短的旅游路线来游历所有的景点，再比如无线通信中的信道编码和解码；很多美妙的算法源于人类对一些挑战自身智力的谜题的思考，比如经典的华容道问题，寻找数独的解法，再比如用程序战胜九段围棋高手等。书中的这些谜题深刻却不枯燥，作者还给出了很多幽默的插图，它适合也值得任何学术背景的人花时间阅读和思考。这让我看出作者写这本书不但花费了很多心血，而且收获了很多欢乐；使用和发现算法是快乐的，这也是我觉得这本书特别美好之处。毕竟人类的阶段就是认识宇宙，了解生命起源，而更高阶段是创造和优雅地解决那些有趣的谜题！
无论作为一个需要使用各种算法的从业人员，还是一个喜欢不停思考有趣问题的人，我都觉得新宇的这本《算法新解》是一本难得的好书。如果可以，我希望能够立刻把全书上传到大脑之中。
——常成博士，4 数网主编
“算法是每个计算机专业学生的理论课、基础课、必修课，也是区分计算机爱好者与专业计算机从业人员的重要课程。现在市面上五花八门的算法书也很多，但是能把算法结合实际应用生动讲解出来的却凤毛麟角。刘新宇的这本《算法新解》让人眼前一亮,简明的文字配上插图和不同编程语言的实现，让算法学习变得轻松有趣。并且，书中的例子都特别贴近应用，电子字典、用户输入匹配等小应用让人感觉算法无处不在。对于每个例子，这本书也会循序渐进给出更加优化的算法，并力求让读者掌握一种解决问题的思路。虽然我在计算专业领域研究开发多年，在读了刘新宇的《算法新解》以后仍然感觉受益匪浅。我也希望本书的每一位读者，无论是刚入门的学生、有多年编程经验的技术人员，还是从事理论研究的科技人员，都能有所收获。”——顾峥博士，LinkedIn高级工程师
“《算法新解》七年磨一剑，作者笔耕不辍，几年来常在TopLanguage邮件列表中放出让大家校对，在程序书泛滥的这个时代尤显难能可贵。书中包含大量插图和公式，又结合C 、Haskell、Python、Scheme等多种编程语言实现，命令式、函数式兼顾，准确细致地描述了大量基本算法和习题。”——宋方睿，谷歌软件工程师、《Haskell趣学指南》译者
“从入行*天起，我们就被告诫“不要重复造轮子”，但是现成的“轮子”总有一天会无法达到要求。硬件提升总也赶不上数据量的增加，产品人员总能提出让人发疯的新需求，这时我们只有理解原理，才能改进甚至发明可用的新‘轮子’。
请不要忘记我们的好奇心。离开了功利的驱使，单纯的获取知识，会是另一种愉悦的精神体验。在阅读这本书时，这种体验将始终伴随着你。” ——陈维扬，小米软件工程师
评论
还没有评论。