编辑推荐
伪代码与多语言实现并存，充分发挥语言特性
理论与实例结合，轻松学习算法与数据结构
内含ACM竞赛趣题和传统趣题，发现算法的乐趣
七年磨一剑，中国高级研发人员重磅力作
媒体推荐
算法是每个计算机专业学生的理论课、基础课、必修课，也是区分计算机爱好者与专业计算机从业人员的重要课程。现在市面上五花八门的算法书也很多，但是能把算法结合实际应用生动讲解出来的却凤毛麟角。刘新宇的这本《算法新解》让人眼前一亮,简明的文字配上插图和不同编程语言的实现，让算法学习变得轻松有趣。并且，书中的例子都特别贴近应用，电子字典、用户输入匹配等小应用让人感觉算法无处不在。对于每个例子，这本书也会循序渐进给出更加优化的算法，并力求让读者掌握一种解决问题的思路。虽然我在计算专业领域研究开发多年，在读了刘新宇的《算法新解》以后仍然感觉受益匪浅。我也希望本书的每一位读者，无论是刚入门的学生、有多年编程经验的技术人员，还是从事理论研究的科技人员，都能有所收获。
——顾峥博士，LinkedIn高级工程师
《算法新解》七年磨一剑，作者笔耕不辍，几年来常在TopLanguage邮件列表中放出让大家校对，在程序书泛滥的这个时代尤显难能可贵。书中包含大量插图和公式，又结合C++、Haskell、Python、Scheme等多种编程语言实现，命令式、函数式兼顾，准确细致地描述了大量基本算法和习题。
——宋方睿，谷歌软件工程师、《Haskell趣学指南》译者
从入行起，我们就被告诫“不要重复造轮子”，但是现成的“轮子”总有一天会无法达到要求。硬件提升总也赶不上数据量的增加，产品人员总能提出让人发疯的新需求，这时我们只有理解原理，才能改进甚至发明可用的新“轮子”。
请不要忘记我们的好奇心。离开了功利的驱使，单纯的获取知识，会是另一种愉悦的精神体验。在阅读这本书时，这种体验将始终伴随着你。
——陈维扬，小米软件工程师
作者简介
刘新宇，1999年和2001年分别获得清华大学自动化系学士和硕士学位，之后长期从事软件研发工作。他关注基本算法和数据结构，尤其是函数式算法，目前就职于中国仓储和物流技术团队。
目录
目录
序一常成博士，4数网主编
序二姚冬，YY直播架构师
前言
第一部分 树
第1章 二叉搜索树：数据结构中的“hello world”3
1.1 定义3
1.2 数据组织5
1.3 插入6
1.4 遍历8
1.5 搜索10
1.5.1 lookup10
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和Patricia65
5.1 整数Trie65
5.1.1 整数Trie的定义67
5.1.2 插入67
5.1.3 查找69
5.2 整数Patricia70
5.2.1 定义71
5.2.2 插入72
5.2.3 查找78
5.3 字符Trie80
5.3.1 定义80
5.3.2 插入81
5.3.3 查找83
5.4 字符Patricia84
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 后缀Trie104
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 Heapify160
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 减小key232
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 信息复用
14.2 解的搜索428
14.2.1 深度优先搜索和广度优先搜索428
14.2.2 搜索最优解468
14.3 小结498
附录 列表500
列表的定义500
列表的基本操作502
变换527
提取子列表536
fold543
搜索和匹配549
zip和unzip555
小结558
参考文献559
索引563
伪代码与多语言实现并存，充分发挥语言特性
理论与实例结合，轻松学习算法与数据结构
内含ACM竞赛趣题和传统趣题，发现算法的乐趣
七年磨一剑，中国高级研发人员重磅力作
媒体推荐
算法是每个计算机专业学生的理论课、基础课、必修课，也是区分计算机爱好者与专业计算机从业人员的重要课程。现在市面上五花八门的算法书也很多，但是能把算法结合实际应用生动讲解出来的却凤毛麟角。刘新宇的这本《算法新解》让人眼前一亮,简明的文字配上插图和不同编程语言的实现，让算法学习变得轻松有趣。并且，书中的例子都特别贴近应用，电子字典、用户输入匹配等小应用让人感觉算法无处不在。对于每个例子，这本书也会循序渐进给出更加优化的算法，并力求让读者掌握一种解决问题的思路。虽然我在计算专业领域研究开发多年，在读了刘新宇的《算法新解》以后仍然感觉受益匪浅。我也希望本书的每一位读者，无论是刚入门的学生、有多年编程经验的技术人员，还是从事理论研究的科技人员，都能有所收获。
——顾峥博士，LinkedIn高级工程师
《算法新解》七年磨一剑，作者笔耕不辍，几年来常在TopLanguage邮件列表中放出让大家校对，在程序书泛滥的这个时代尤显难能可贵。书中包含大量插图和公式，又结合C++、Haskell、Python、Scheme等多种编程语言实现，命令式、函数式兼顾，准确细致地描述了大量基本算法和习题。
——宋方睿，谷歌软件工程师、《Haskell趣学指南》译者
从入行起，我们就被告诫“不要重复造轮子”，但是现成的“轮子”总有一天会无法达到要求。硬件提升总也赶不上数据量的增加，产品人员总能提出让人发疯的新需求，这时我们只有理解原理，才能改进甚至发明可用的新“轮子”。
请不要忘记我们的好奇心。离开了功利的驱使，单纯的获取知识，会是另一种愉悦的精神体验。在阅读这本书时，这种体验将始终伴随着你。
——陈维扬，小米软件工程师
作者简介
刘新宇，1999年和2001年分别获得清华大学自动化系学士和硕士学位，之后长期从事软件研发工作。他关注基本算法和数据结构，尤其是函数式算法，目前就职于中国仓储和物流技术团队。
目录
目录
序一常成博士，4数网主编
序二姚冬，YY直播架构师
前言
第一部分 树
第1章 二叉搜索树：数据结构中的“hello world”3
1.1 定义3
1.2 数据组织5
1.3 插入6
1.4 遍历8
1.5 搜索10
1.5.1 lookup10
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和Patricia65
5.1 整数Trie65
5.1.1 整数Trie的定义67
5.1.2 插入67
5.1.3 查找69
5.2 整数Patricia70
5.2.1 定义71
5.2.2 插入72
5.2.3 查找78
5.3 字符Trie80
5.3.1 定义80
5.3.2 插入81
5.3.3 查找83
5.4 字符Patricia84
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 后缀Trie104
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 Heapify160
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 减小key232
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 信息复用
14.2 解的搜索428
14.2.1 深度优先搜索和广度优先搜索428
14.2.2 搜索最优解468
14.3 小结498
附录 列表500
列表的定义500
列表的基本操作502
变换527
提取子列表536
fold543
搜索和匹配549
zip和unzip555
小结558
参考文献559
索引563
| ISBN | 9787115440358 |
|---|---|
| 出版社 | 人民邮电出版社 |
| 作者 | 刘新宇 |
| 尺寸 | 16 |