一夜春风，万树梨花

Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein合著的《算法导论（第三版）》一书，涵盖了我们常用的大多数算法，并系统性地对各个算法从概念、性能、优劣等各方面进行了深入而有见地的分析与讲解，全书近800页。这本书的四个作者全部是全球大学的博士加教授，所以这本书有再大的声响，也实在不算奇怪。

Robert Sedgewick、Kevin Wayne合著的《算法（第四版）》也大概在同一时期出版，也许是由于作者比上面那本书少了两位，全书只有600来页，虽然拿在手里还是不轻，但无论如何，能够在那个年代给出算法的Java实现，也真是善莫大焉。

以上两本书的出版时间，大概都是在2012年。此后，随着国内软件技术水平的飞速提高，在算法领域也涌现出不少优秀的图书作品，有大话的，有啊哈的，有漫画的。总之，但凡能为读者降低一丁点儿学习难度的算法书，都受到了读者喜爱。

但上述两本书的地位却从未受到过实质性挑战，被读者奉为算法学习之圭臬，长期占据算法类图书排行榜前两名。这种现象的产生，可能包含了上述提到的种种原因，或许也有致敬经典或购书的从众心理。但不得不说，粗略算来，以上两本书离出版时间迄今已经8年有余，8年时间，当时生的孩子现在应该可以打酱油了。而两三斤的重量，也不是普通算法练家子敢于承受的—无论是心理还是身体。

算法，承载着无数程序员的追求与梦想，纵是被虐千百遍，依然待之如初恋。算法在磨砺着众多程序员心智的同时，也在被无数程序员吸收、质疑、优化。铁猛，便是这队伍中的一员。

说起铁猛，不少资深的程序员都熟悉。大概在以上两本算法图书出版的同一时期，铁猛的本技术著作《深入浅出WPF》面世，这本书，也是近10年来铁猛写过的的一本书。尽管已经重印十余次，但直到现在，该书依然有读者在不断购买。近10年来，WPF的版本已历经数次更新，市场上讲解WPF版本技术的图书也比比皆是。作为该书当时的编辑，我确信该书在技术之外，一定有些其他可以触动读者的因素，这或许包括其治学的态度，或许包括对其文字的欣赏，或许还包括某些只有程序员可以体会的特别的原因。我只知道，因为这本书的积累，铁猛的功力达到了一个相当的高度，从而得以顺利进入美国微软。

不久前的某一天，身在美国的铁猛联系我，说他在准备面试的过程中，总结了一些关于算法的内容，想让我帮忙掌掌眼。我嘴上是淡淡的答应，心里却着实来了精神。以我对铁猛的了解，他主动拿出去让人掌眼的，一定是他用心、值得与技术社区分享的好东西。

他把这些关于算法的内容发给了我，也就是本书的初稿，基本上也是本书的终稿。我把本书的一些审读体会讲给大家。

首先，本书与上述提到的《算法导论》及《算法》相比，是一本让你有条件可以倒背如流的书。所谓的有条件，一是书不能太厚，六七百页的书，读一遍都困难，别说倒背了；二是得能够让人真正深刻理解，对于理解不了的书不要说百十来页，就是背上一页都难于上青天；三是要有倒背的必要，你若对任一经典算法能信手拈来，相信你一定可以得到一个全球IT企业Top 10的Offer，面对这种投资产出比，背几个算法，有何不可？四是要背就得背一本值得背的书。

当然，请读者背一本书只是个玩笑，每位读者对一本书的价值，都有自己的评定。

本书主题为“算法之禅”。算法，不要说是照本宣科地讲，哪怕深入浅出地讲，我感觉与这个“禅”的意境还是云泥之别。

禅是诸法因缘生。算法领域，经典笼罩，读者能发现此书，为“缘”。

禅是一沙一世界。如果能从作者的某句话中得到一个顿悟，能从一个算法的讲解中体会到作者之所以达到某种高度的内因，这书是100多页还是800多页，也就无关紧要了，你必将拥有世界。

算法像一个棒槌，中间容易两头难。假设天下算法共有九九八十一种，你若想创造出第八十二种，这比较难，建议随缘；若想把这八十一种算法都弄明白怎么回事，不是太难，但仅弄明白怎么回事，除了侃大山外却没什么别的大用；要把任意算法都能信手实现，这个也比较难，但确是值得下些功夫的，因为这类人在代码江湖中不足十之一二，一旦入围就是值得仰望的存在。

可见，算法学习的核心，就是算法的实现。不能实现、面试时不能实现、面试时稍加变化就不能实现，这代表了算法水平的地下三重天，反之则是地上三重天。而在实际工作中，面对实际应用场景，一个恰当的算法能不能实时地从脑海中跃然而出并就地化为代码，这是我们真正的目标。

而任何算法的实现，世界上只有两条路：递推，或者递归。

递推与递归都能完成算法的实现，各有所长又各有局限，当你既可以用递推的思想来实现算法，又可以用递归思想来实现算法，你就实现了Offer自由。

而本书，不但对算法进行了完整的实现，更是用递推与递归的方法进行了双重实现。从这个角度，本书还当真是世界无二了。

我真诚向大家推荐这本书，希望大家有缘领略铁猛老师优雅的文字、极美的代码、深邃的思想，在本书的引领下，实现Offer自由。

十年寒窗，只待一夜春风，万树梨花。

本书编辑 周春元

算法是个有趣的东西—针对某个问题设计算法的时候，不会的人感觉像“大海捞针”，而会的人则感觉像“一苇渡江”。高手的头脑里都有一张“算法地图”，算法之间不是孤立的，而是彼此连通的。算法之间的内在联系有很多，但挖掘到根源上，就是递推与递归两种思想。本书从深度解析递推和递归这两个基本算法思想开始，用它们贯穿起了《算法导论》中的几十个经典算法，包括排序、查找、回溯、贪心、分治、动态规划、图算法等。 本书成稿自作者的教案，秉承了作者一贯的风趣幽默又不失严谨的写作风格，同时融入了学习心理学和认知科学的实践原理。作者的诸多学生在参加完以本书内容为蓝本的集训后进入了微软、脸书、亚马逊、领英、甲骨文等公司，所以本书是经过千锤百炼的一线教学成果。本书适合于所有想通过学习算法来精进自己编程能力的读者。为了倾听读者们的心声、不断完善这本书，作者热切地期待大家与他在领英上建立联系。在那里，作者还将源源不断地与读者们分享种类教学资源和工作机会。作者的领英首页是https:www.linkedin.cominhexagons。

刘铁猛，高级软件工程师，技术作者、译者、教育者，现就职于亚马逊（美国）。曾就职于微软（美国），著有《深入浅出WPF》一书，销量数万册。精心制作的《C#语言入门详解》视频课程点击量超500万次，是深受好评的中文C#教程。他的多套视频教学已被微软收录为官方认证课程。他的所有作品风格一致：内容详实准确、语言风趣幽默、说理深入浅出，被学习者们奉为佳作。

致谢

一夜春风，万树梨花

第00章  开篇绪言

缘起 1

预备知识 3

第01章  思想与实现

思想 6

实现 8

准备一棵树 9

用递推代码实现递推思想 11

用递归代码实现递推思想 13

用递归代码实现递归思想 15

“好”的递归与“坏”的递归 16

用递推代码实现递归思想 20

思考题 23

第02章  回溯：上古神话中的算法

回溯式递归的基本原理 24

示例1 25

示例2 26

神话故事中的算法 27

迷宫设计入门 28

探寻迷宫中的路径 29

用递推（循环）代码实现回溯 32

思考题 33

第03章  动态规划：动机决定性质

什么是动态规划 35

透彻理解动态规划 36

递推版动态规划 37

递归版动态规划 39

陷阱：这不是动态规划！ 42

贪心也要动脑子 43

更上层楼：让规划“动态”起来 46

切年糕 46

接订单 48

听讲座 56

思考题 60

动态规划哲思 60

第04章  排序：算法皇冠上的明珠

游乐园：O(n^2)的简单排序们 63

选择排序 63

冒泡排序 64

插入排序 66

以空间换时间：归并排序 66

看运气的快速排序 68

两全其美：堆排序 71

什么是“堆” 71

构建大/小根堆 72

利用“大根堆”进行原地排序 75

利用“小根堆”生成升序数组 75

思考题 76

第05章  查找：来而不往非礼也

二分查找 78

在已排序的数组上 79

在平衡二叉搜索树上 80

线段树：化繁为简 81

构建线段树 82

查询子段和 84

字典树：字母大接龙 86

递推版实现 87

递归版实现 89

并查集：朋友的朋友是朋友 90

第06章  图：包罗万象

图的表达 94

邻接列表 95

邻接矩阵 97

应对向、权、环的变化 98

思考题 100

图的遍历 100

广度优先遍历 101

深度优先遍历 103

递推版深度优先遍历 105

向、权、环对遍历的影响 106

顶点的连通性 107

有无权重对连通性的影响 109

有无向对连通性的影响 110

环对连通性的影响 113

强连通性组件 113

Kosaraju-Sharir算法 114

图上的路径 116

BFS式路径搜寻 118

DFS式路径搜寻 119

自底向上式路径搜寻 119

回溯式路径搜寻 121

获取环路 122

思考题 123

短路径 124

Dijkstra短路径算法 125

Bellman-Ford短路径算法 129

Floyd-Warshall短路径算法 131

小生成树 133

构建有权无向图 134

Prim算法 136

Kruskal算法 137

流：超时空移花接木 138

余量边，反向边，余量网络，增益路径 139

容量返还 140

Ford-Fulkerson算法实现 143

小割：流量的瓶颈 145

拓扑排序 147

生成入度图与出度图 148

理解顶点的入度 149

递推实现 150

递归实现 151

思考题 152

后记

算法是个有趣的东西—针对某个问题设计算法的时候，不会的人感觉像“大海捞针”，而会的人则感觉像“一苇渡江”。高手的头脑里都有一张“算法地图”，算法之间不是孤立的，而是彼此连通的。算法之间的内在联系有很多，但挖掘到根源上，就是递推与递归两种思想。本书从深度解析递推和递归这两个基本算法思想开始，用它们贯穿起了《算法导论》中的几十个经典算法，包括排序、查找、回溯、贪心、分治、动态规划、图算法等。 本书成稿自作者的教案，秉承了作者一贯的风趣幽默又不失严谨的写作风格，同时融入了学习心理学和认知科学的实践原理。作者的诸多学生在参加完以本书内容为蓝本的集训后进入了微软、脸书、亚马逊、领英、甲骨文等公司，所以本书是经过千锤百炼的一线教学成果。本书适合于所有想通过学习算法来精进自己编程能力的读者。为了倾听读者们的心声、不断完善这本书，作者热切地期待大家与他在领英上建立联系。在那里，作者还将源源不断地与读者们分享种类教学资源和工作机会。作者的领英首页是https:www.linkedin.cominhexagons。

刘铁猛，高级软件工程师，技术作者、译者、教育者，现就职于亚马逊（美国）。曾就职于微软（美国），著有《深入浅出WPF》一书，销量数万册。精心制作的《C#语言入门详解》视频课程点击量超500万次，是深受好评的中文C#教程。他的多套视频教学已被微软收录为官方认证课程。他的所有作品风格一致：内容详实准确、语言风趣幽默、说理深入浅出，被学习者们奉为佳作。