算法技术手册
打造鲁棒性优秀的软件需要用到高效的算法，然而程序员们却对此知之甚少。新版的《算法技术手册》介绍了用于解决各种类型问题的已有算法，并帮助读者挑选和实现最适合自身需要的算法。不仅如此，书中还提供了恰到好处的数学知识来帮助读者理解和分析算法的性能。
本书侧重应用多于理论且规范严谨。书中提供了用多种程序设计语言实现的文档化的实际代码解决方案。此外，新版还增加了用Python实现的10多种新算法、Voronoi图算法实现以及包括R树（R-Trees）和四叉树（Quadtrees）在内的空间树结构等内容。
通过阅读本书，你将可以：
■ 解决新的编码问题，提升现有解决方案的性能。
■ 快速定位与问题相关的算法，并挑选最佳算法。
■ 获取带有实现技巧提示的采用C、C++、Java和Python实现的算法解决方案。
■ 学习算法的预期性能和最佳性能所需要的条件。
■ 使用高级数据结构提升算法效率。

“这本书之所以如此出色，有三个原因：首先，算法和数据结构的介绍图文并茂、易于查找。其次，行文生动，没有过于学术化。最后，书中一直不断地强调算法性能的基准测试。阅读此书将会永远地改变你使用数据结构的方式。”
——Richard Resnick
GQLife Science首席执行官

George T. Heineman是美国伍斯特理工学院计算机科学系的一名副教授, 曾任国际组件软件工程研讨会的议程主席。
Gary Pollice是美国伍斯特理工学院的一名实践教授，与他人合著了《深入浅出面向对象与设计》（Head First Object Oriented Analysis and Design）一书。
Stanley Selkow有着40年的大学教龄，他所从教的大学遍布加拿大蒙特利尔、中国重庆、瑞士洛桑和法国巴黎。

修订一本书向来都是一项艰巨的任务。我们既希望保留第1版（于2009年出版）中的精华，也希望弥补其中的一些不足并增加一些新的篇幅。在第2版中，我们延续了第1版中列出的原则，包括：
使用实际代码而非伪代码来描述算法。
将算法独立于解决的问题之外。
恰到好处地介绍数学知识。
以经验主导支撑数学分析。
在更新修订过程中，我们精简了文字描述，简化了一些布局，从而有助于补充新的算法和其他内容。我们相信，从概括的角度介绍计算机科学的一个重要领域，会对实用软件系统有着深远影响。
第2版的变动
在修订过程中，我们遵循以下原则：
挑选新的算法
在第1版出版之后，我们常常会收到一些留言，比如，“为什么漏掉了归并排序？”或“为什么没有介绍快速傅里叶变换（Fast Fourier Transform，FFT）？”虽然我们无法满足所有这些要求，但第2版还是增添了一些新的算法，包括：
Fortune算法，它用于计算点集的Voronoi图。
归并排序，既包括针对内存数据的内部排序，也包括外部文件的外部排序。
多线程快速排序。
AVL平衡二叉树实现。
新的章节（第10章）用于介绍空间算法，包括R树（R-Tree）和四叉树（Quadtree）。
总的来说，本书差不多介绍了40种核心算法。
简化描述
为了方便新增内容，我们几乎对第1版的所有内容进行了修订，简化了算法描述框架，并且减少了一些附带描述。
增加Python实现
我们并没有使用Python重新实现已有的算法，而是特意为大部分新增的算法提供了Python实现。
管理代码资源
第1版中的代码是通过ZIP压缩包文件的方式提供的。之后，我们就迁移到了GitHub代码库。这些年里，我们不仅提高了代码质量和增加了相关文档，还加入了在第1版出版后撰写的一些博客文章。代码库中不仅拥有超过500个的单元测试用例，还使用代码覆盖工具以确保99%的Java代码都被覆盖。目前代码库中的代码行数总计超过11万行。
目标读者
我们期望这本书能够成为读者的一本主要参考书，方便查阅如何实现和使用某些算法。书中了介绍了一系列用于解决问题的已有算法，并遵循以下的一些原则：
在介绍每种算法时，我们会使用一种固定格式的模板。这种模板可以帮助恰当地设计每一次的讨论和解释每种算法的要点。
我们使用了不同的语言实现了每种算法（包括C、C++、Java和Python）。得益于此，我们能够使用读者熟悉的编程语言对算法进行详细的讨论。
我们描述了每种算法的预期性能，并根据经验加以证明。
我们希望这本书对软件工程师、程序员以及设计师有所帮助。为了实现目标，你需要使用大量关于实际解决方案和算法的资源，才能解决手头的实际问题。你已经知道了如何使用多种语言编写一个程序，也了解了计算机科学中的关键数据结构（例如数组、链表、栈、队列、散列表、二叉树以及有向图和无向图），但是你并不需要亲自实现这些数据结构，因为可以在代码库中找到它们。
我们希望，读者能从这本书中学习到如何选择和测试解决方案来快速高效地解决问题，同时也能学习到一些高级数据结构和使用标准数据结构的新方法来提高程序的性能。而解决问题的能力高低就取决于所选择算法的效率高低。
本书体例
在印刷上的一些例行惯例：
代码（Code）
所有代码示例都使用这种字体。
这些代码都是直接取自代码库，是现实中使用的代码。此外，书中所有代码清单都进行了“美化处理”以强调对应程序设计语言的语法。
斜体（Italic）
斜体用于表示描述算法和数据结构的关键术语，也会用于指代示例伪代码描述中的变量。
等宽字体（Constant Width）
等宽字体用于表示程序实现中的实际软件元素，例如Java 类、C语言实现中的数组名以及常量（如true或false）。
在本书中，我们引用了大量的书籍、文章和网址。这些引用都用括号标注出来，例如（Cormen等，2009），并且在每章末尾都会列出本章所使用的参考文献。若参考引用紧跟在作者姓名之后，则不会重复其姓名。例如，当提到Donald Knuth的《Art of Computer Programming》一书时，括号中仅附带出版年份。
本书中的所有URL于2016年1月验证过，并且我们所选用的URL在近期均可用。除此之外，我们也用到了较短的URL，如http://www.oreilly.com，此类URL会直接出现在正文中，也会出现在脚注和每章末尾的参考文献中。
代码使用说明
补充资料（代码示例、练习题等）可以从https://github.com/heineman/algorithms-nutshell-2ed下载。
本书的目的是帮助读者更好地完成工作。通常来说，你可以在自己的程序和文档中直接使用本书提供的示例代码。除非需要大量复制这些代码，否则你不需要联系我们获得许可。例如，如果你所编写的程序使用了本书中几段代码，则无须获取许可。但是如果作销售或者发行光盘之用，则需要许可。引用本书和使用书中的样例代码回答问题也无须获取许可。但是如果你在自己的产品文档大量地使用本书中的代码，则需要许可。
我们希望但是不强制要求标明归属。一个归属说明通常包括标题、作者、出版商和ISBN 。例如，“George T. Heineman、Gary Pollice 和Stanley Selkow 编写的《Algorithms in a Nutshell, Second Edition》。C2016 George Heineman、Gary Pollice and Stanley Selkow，978-1-4919-4892-7。”
如果你觉得使用代码的情况超出了我们所允许的范围，请与我们联系：permissions@oreilly.com。
联系我们
对于本书，如果有任何意见或疑问，请按照以下地址联系本书出版商。
美国：
O''Reilly Media，Inc.
1005 Gravenstein Highway North
Sebastopol，CA 95472
中国：
北京市西城区西直门南大街2号成铭大厦C座807室（100035）
奥莱利技术咨询（北京）有限公司
我们为本书提供了网页，该网页上面列出了勘误表、范例和任何其他附加的信息。您可以访问如下网页获得：
http://bit.ly/algorithms_nutshell_2e
要询问技术问题或对本书提出建议，请发送电子邮件至：
bookquestions@oreilly.com
要获得更多关于我们的书籍、会议、资源中心和O扲eilly网络的信息，请参见我们的网站：
http://www.oreilly.com
http://www.oreilly.com.cn

致谢
在此，我们真诚地感谢本书的审阅人员，感谢他们对于本书细节的关注以及提出的宝贵建议，这些建议有助于提高本书的质量。特别感谢在第1版中给予我们帮助的Alan Davidson、Scot Drysdale、Krzysztof Duleba、Gene Hughes、Murali Mani、Jeffrey Yasskin和Daniel Yoo，以及第2版中给予我们帮助的Alan Solis、Robert P. J. Day和Scot Drysdale。
George Heineman想要感谢那些带领他走入算法领域的人，包括Scot Drysdale教授（美国达特茅斯学院）和Zvi Galil教授（美国哥伦比亚大学，现任美国佐治亚理工学院计算学院系主任）。一如既往，George也非常感谢他的妻子Jennifer和他的孩子们——Nicholas（他现在已经开始学习编程了）和Alexander（他喜欢用这个版本的打印稿折纸玩）。
Gary Pollice想要感谢他的妻子Vikki陪伴他走过46年的美好时光。他同样感谢WPI计算机科学系提供给他的优质工作和幽雅环境。
Stanley Selkow想要感谢他的妻子Deb。这本书是在他们相伴走过的时光中的又一个结晶。

计算机\算法

要开发出鲁棒性优秀的软件，无疑要用到高效的算法，然而很多程序员对算法都是一知半解，真正学好算法的并不多。本书讲解了许多现有的算法，可用于解决各种类型问题。通过阅读它，你将学会如何选择和实现正确的算法来达成自己的目标。另外，书中提供的相关数学知识深浅适中，足够使你可以理解和分析算法的性能。
在理论和应用两个而言，本书更侧重于后者且注重结构的规范严谨。本书提供了用多种程序设计语言实现的文档化的实际代码解决方案。此外，本书还增加了用Python实现的十多种新算法、Voronoi图算法实现以及包括R树和四叉树在内的空间树结构等内容。

通过阅读本书，你将可以：

•解决新的编码问题，提升现有解决方案的性能。
•快速确定与问题相关的算法，并挑选最佳算法。
•获取带有实现技巧的算法解决方案（采用C、C++、Java和Python实现）。
•了解算法的预期性能和最佳性能所需要的条件。
•使用高级数据结构提升算法效率。

“本书如此出色的原因有三个：首先，算法和数据结构的介绍图文并茂易于查找；其次，作者行文生动，没有过于学术化；最后，本书一直不断地在强调算法性能的基准测试。如果你活在当下，阅读本书将会永远地改变你使用数据结构的方式。”
—— Richard Resnick， GQLife Science首席执行官

[美]乔治 T.海涅曼（George T. Heineman），加里?波利切（Gary Pollice），斯坦利?赛克欧（Stanley Selkow）著：
George T. Heineman 伍斯特理工学院计算机科学系副教授, 曾于2005年任国际组件软件工程研讨会的议程主席。 Gary Pollice 伍斯特理工学院的实践教授，《深入浅出面向对象与设计》（Head First Object Oriented Analysis and Design）的合著者。 Stanley Selkow 有着40年的大学教龄，他所从教的大学遍布于加拿大蒙特利尔、中国重庆、瑞士洛桑和法国巴黎。

杨晨　曹如进　译：暂无简介

算法，神秘而晦涩的词汇。算法是计算机科学中最重要同时也是最基础的一环。在学习计算机之初，我们就深知算法是整个计算机科学的核心。然而，直至我们工作数年后，能够真正学好算法的却依旧是凤毛麟角。这并不是计算机教育的错，也不是计算机从业人员的错，更不是算法的错。长久以来，算法就像古老的咒语般难懂，其背后高深的数学知识更让人望而生畏。其实，我们始终没有找到一条从理论走向实践的路。
在这里，我们很高兴能向大家介绍本书。它是一本不可多得的好书，能够帮助你学好算法。
本书的三位作者是美国伍斯特理工学院的教授，其中George T. Heineman毕业于美国达特茅斯学院和哥伦比亚大学，曾经获得过GE、IBM和AT&T的研究奖金，在软件工程方面有独到的见解。而Gary Pollice 曾经供职于Rational Software、Sun等多家巨头公司，在工业界有着丰富的经验，擅长将学术和工业结合起来。Stanley Selkow毕业于美国卡内基梅隆大学和宾夕法尼亚大学，擅长图论和算法设计。
本书由伍斯特理工学院这三位计算机理论专家合著，其中展示了工业界和学术界对算法的不同看法，以及如何高效地将理论和实践结合起来。
本书可供本科生以及程序设计人员参考使用，也适用于产品和项目管理人员。由于译者的知识和经验有限，翻译中难免有疏漏或不足之处，敬请广大读者批评指正。

杨晨 曹如进

前言 1
第1章 用算法的眼光去看问题 7
1.1 理解问题 7
1.2 简单解法 8
1.3 高明做法 9
1.4 总结 13
1.5 参考文献 13
第2章 算法的数学原理 14
2.1 问题样本的规模 14
2.2 函数的增长率 15
2.3 最好、最坏和平均情况下的性能分析 18
2.4 性能指标 23
2.5 基准测试 34
2.6 参考文献 36
第3章 算法基础 37
3.1 算法模板的格式 37
3.2 伪代码模板的格式 38
3.3 实验评估的格式 39
3.4 浮点计算 39
3.5 算法举例 43
3.6 常用方法 47
3.7 参考文献 53
第4章 排序算法 54
4.1 概述 54
4.2 移位排序 58
4.3 选择排序 61
4.4 堆排序 62
4.5 基于分区的排序算法 68
4.6 不基于比较的排序算法 74
4.7 桶排序 74
4.8 使用额外存储空间的排序算法 80
4.9 字符串基准测试结果 84
4.10 分析技术 86
4.11 参考文献 88
第5章 搜索算法 89
5.1 顺序搜索 90
5.2 二分搜索 93
5.3 散列搜索 97
5.4 布隆过滤器 111
5.5 二叉搜索树 114
5.6 参考文献 126
第6章 图算法 127
6.1 图 127
6.2 深度优先搜索 131
6.3 广度优先搜索 136
6.4 单源顶点最短路径 140
6.5 针对稠密图的Dijkstra算法 145
6.6 比较单源顶点最短路径的各种方案 149
6.7 所有点对最短路径 151
6.8 最小生成树算法 155
6.9 关于图的最后一些想法 159
6.10 参考文献 160
第7章 AI寻路 161
7.1 博弈树 161
7.2 寻路算法的概念 165
7.3 Minimax 166
7.4 NegMax 171
7.5 AlphaBeta 174
7.6 搜索树 180
7.7 深度优先搜索 183
7.8 广度优先搜索 188
7.9 A*搜索 191
7.10 比较搜索树算法 201
7.11 参考文献 203
第8章 网络流算法 206
8.1 网络流 208
8.2 最大流 209
8.3 二分图匹配 219
8.4 对于增广路径的深入思考 222
8.5 最小费用流 226
8.6 转运问题 227
8.7 运输问题 228
8.8 任务分配问题 228
8.9 线性规划 230
8.10 参考文献 231
第9章 计算几何 232
9.1 问题类型 232
9.2 凸包 236
9.3 凸包扫描 237
9.4 计算线段交点 244
9.5 线段扫描 244
9.6 Voronoi图 253
9.7 参考文献 265
第10章 空间树结构 266
10.1 最近邻查询 267
10.2 范围查询 268
10.3 交集查询 268
10.4 空间树 268
10.5 最近邻查询 271
10.6 范围查询 281
10.7 四叉树 287
10.8 R树 292
10.9参考文献 303
第11章 新兴算法 304
11.1 特定情形下的衍生算法 304
11.2 近似算法 304
11.3 并行算法 310
11.4 概率算法 314
11.5 参考文献 321
第12章 尾声：算法原理 322
12.1 了解数据 322
12.2 将问题分解成更小的问题 323
12.3 选择正确的数据结构 324
12.4 空间换时间 325
12.5 构造一个搜索 326
12.6 将问题归约为另一个问题 326
12.7 编写算法难，测试算法更难 327
12.8 在可能的情况下接受近似解 328
12.9 增加并行化以提升性能 328
附录A 基准测试 331