《算法》第4版 导读
《算法》第4版
之前在微博 @算法时空 做了一次电台，花了一个多小时谈了一下Sedgewick和Wayne所著的畅销书《算法》第4版(影印版和中译版均由人民邮电出版社出版)，特别是按照这本书的目录给出了导读。觉得有必要把文字整理出来，希望对阅读此书的朋友有所帮助。
历史
《算法》第4版这本书其实不太像传统的算法书，但是它很畅销！实际上，这不仅因为它有接近四十年的传承，多次修订不断进化方才如此，而是作者的最新教学理念的展现。
算法分析大师Sedgewick一开始写这个系列的书，心中就有宏伟的念头，要传承Knuth的衣钵，因为Sedgewick作为Knuth的学生，他觉得当仁不让，所以雄心勃勃。其实Sedgewick刚开始开始写《算法》的时候，也就是《算法》第1版，内容相对比较简单。随着时间流逝，第2版和第3版不断进化，而此时这套书的难度到达了巅峰。
实际上《算法》第3版出过很多语言版本，比如C++, C, Java版(国内高教出版社影印过)。最开始是C, C++然后是Java，其实Sedgewick想把Knuth难度极高的《计算机程序设计艺术》三卷书浓缩成《算法》的上卷(或称Part 1-4)，并用不同语言来实现，从而形成更适合教学的优秀教科书。这本上卷名为《算法与数据结构基础、排序和查找》，其内容非常接近《计算机程序设计艺术》的第1卷(基本算法)和第3卷(排序与查找)，去掉了第2卷(因为一般大家都不看第2卷，里面讲的是随机数生成等内容)。《算法》的下卷(或称Part 5)，从《计算机程序设计艺术》往下开始写，专讲图算法，虽然比上卷薄，但内容依然很丰富。
变革
Sedgewick花了这么多年将这套《算法》做到了很高的层次，为什么写到第4版的时候，思路有了一个如此大的转变呢？实际上他在前言里说到，第4版的难度相当于第1版或者第2版的样子，回复到一个基础简单的水平，也是Addison-Wesley出版社的Peter Gordon建议他要back to the basics。
《算法》第4版的核心写作思想就是降低算法学习的难度，这是一种大势所趋，实际上写到了巅峰没几个人能看懂。就拿Knuth的三卷《计算机程序设计艺术》来说吧，很多人看到数学知识太繁杂，算法分析长篇大论，而且Knuth有点强迫症(不过他创造的TeX排版确实太好了)，书里用MMIX，读者还得学这个。实际上，《计算机程序设计艺术》这样一个高大上的体系让Knuth奉献了一生，特别是里面的算法分析，数学推导特别多。但是，Knuth的得意门生Sedgewick在这样的时代却写了一本难度比较低的算法书，实际上是有很多无奈的。
Google的Peter Norvig说Knuth的三卷《计算机程序设计艺术》可以垫高显示器，由于盒装可以从里面抽出一本随时翻阅。但更多的人拿这个垫显示器估计不会拿出来看了。
前几年的Sedgewick的个人网站还有《算法》第3版后续部分也就是组合算法部分的写作计划，和老师Knuth的思路完全一样。这两年这部分写作计划似乎取消了，可能写出来太耗时，曲高和寡没人看。最终Sedgewick决定让算法成为新时代大家都能接受的东西，切实能够提高程序员水平，而不是高深的理论和繁难的技术。老实说，很多人根本用不到那么多算法，所以《算法》第4版看似思路清奇但合情合理。
《算法》居然没有讲动态规划，你说这叫算法书吗？当然可以叫算法书，它其实就不太注重动态规划这些内容，其实普通人也用不太上。
另外，复杂的数学语言《算法》第4版里都没有，而Sedgewick本人算法分析功底相当深厚。我相信他这样的大师，肯定能了解普通人接受起来有困难，所以就放下了自己擅长的理论分析。所以，经过四十年风风雨雨，最后变成了《算法》第4版，精选了普通程序员确实能用的内容，确实不易。
这本书对我的教学观有很大的影响，也激发了我开设“算法时空”知识星球。以前我讲算法的时候，没事喜欢推导一下大O记号之类，动不动写个公式求个极限，给出比较高深的证明，可能是受到《算法导论》这种书的影响。但我现在好像越讲越简单了，力图让大家多少有点收获吧。
Sedgewick在写这本书的时候，得到了第二作者Wayne的大力协助。Wayne是个艺术天赋很高的人，不太醉心于科研而特别喜欢讲课，他博士师从康奈尔大学的Tardos，毕业之后就一直积极开展教学工作，另外还给Kleinberg和Tardos的《算法设计》做了课件(官方指定版)，可能Wayne的课件做得太好了吧。所以《算法》第4版排版特别清新，而且是双色印刷，Wayne绝对功不可没。另外，国内影印版印刷质量很不错，我感觉纸张比原版还要厚实，可能原版有点薄还有反光，不知道纸张到底如何选取的。
Kevin Wayne is the Phillip Y. Goldman Senior Lecturer in Computer Science at Princeton University, where he has taught since 1998, earning several teaching awards.
下面来看看《算法》第4版的构成，从目录讲起。
第1章 基础知识
1.1 编程模型，主要讨论Java基础知识和二分查找。因为这本书前期有Java程序设计的课程，所以1.1篇幅很短。主要是Java程序员太多了，所以Sedgewick没有在《算法》第4版用C++这样的语言。顺便提一下，现代C++如果只用简单的语法部分也不是特别难，而且性能非常优秀。
1.2 数据抽象，也就是所谓抽象数据类型(ADT)。其实抽象数据类型在数据结构课程里都学过，但很多人对它的理解不深刻，处理算法问题应该在抽象数据类型的层次上来做。比如你拿到了集合这样的抽象数据类型，所有数据在里面，而集合是个黑盒我们不用操心，只需要调用集合的接口来使用即可。其实数据结构教学的趋势早已如此，不过国内的教学还没有完全与之一致。有了抽象数据类型之后，所有的处理都在抽象数据类型上展开，我们不需要会实现数据结构，只要能用抽象数据类型并且知道其原理和性能即可，也就是接口与实现分离。
1.3 这节是与传统数据结构讲解完全不一样的地方，以前大家都会讲很多数据结构，而实际中真正有用的却不是那么多。《算法》第4版就精选了包、队列和栈。包就是不用操心其中元素次序的抽象数据类型，放进去当储藏室就可以了，内部实现其实是链表但不提供删除。队列和栈很常用，我们就不多说了，另外如何高效实现队列我们其实也不用操心。所以，《算法》第4版一开始就抽象和提炼了三个抽象数据类型(注意不是数据结构)，有了抽象数据类型的基础就可以无脑使用，但是要知道队列是FIFO而栈是LIFO的特性。这一节相当赞，一开始学习不会让读者涉猎太多的数据结构，学习难度大大降低。
说实话《算法》第4版的写作思路和当前的现实有关，很多人不愿意去学习那些复杂繁琐的东西，这是大趋势。怎么办呢？可以简化内容去讲一些最有用的东西，把精力投入其它事情上去，初学数据结构要掌握的从原来的复杂多样到现在的简单明了，就讲三个！
1.4 算法分析。这节篇幅非常短，不到30页。你可以想象这样一位算法分析大师在写本节的时候，是什么样的心情。明明有很多想写出来的公式，很多想告诉学生的高深内容，但Sedgewick一个都不写。他完全没有写从理论到理论的模型，也就是《算法导论》还有Aho等人的《算法设计与分析》那种体系，这些书首先考虑三种情况(最坏、最好和平均)，以大O记号描述，并主要以最坏情况来讨论，Sedgewick在《算法》第4版里特别隐忍，这是不太容易的。大部分在算法分析上有所造诣的人可能都忍不住想讲解这些内容，但是Sedgewick就忍住了。他怎么做的呢？偏重于科普，让读者了解物理直觉。只要知道大概什么样的算法更快、什么更慢，这就可以了。Sedgewick用了一种做实验的方法，观察算法的运行快慢并建立模型。可以看到《算法》第4版里只提到量级(实际上接近于Theta记号)，连大O记号都不用，只用简单语言简化描述，并用图示刻画函数的增长，另外用加倍实验直观展示了增长量级。一言以蔽之，让读者知道只需要了解这么多就可以了。这种想法看起来很奇怪，但其实很有道理，因为平时能用到的大O记号就那么几种，知道它们就可以了，不用太过于深入理论知识，顶多再了解一些极限的求解即可。我觉得，对于算法分析大师来说写这节真的很痛苦。不过Sedgewick把基本思想写进去了，而且用简单语言描述。《算法》第3版还是写了很多算法分析的基础知识，还有递推式的内容，但《算法》第4版全都去掉了。尽量用通俗的语言让更多人了解算法分析。
一般算法书上都会对各种不同量级的实测时间给出直观的例子。对于较大的问题规模：线性算法比较快，线性对数算法也不错，平方算法慢多了，指数算法永远没法完成。
1.5 有了前面数据结构的内容和算法分析的基础，接下来马上讲实际案例可以让人体会理论的力量。这节讨论了合并—查找算法，也就是如何快速实现等价类，所用的数据结构看起来是树，但实际只需要父亲结点数组就可以描述。可以看出，用了优秀的算法可以极大地提升性能。其实合并—查找的思路和想法都很朴素简单，但算法分析特别困难，也就是那种看似很简单其实不然的典型实例。Sedgewick用这个很好的实例来说明，好的算法是怎样能提升性能的。实际上, 《算法》第3版就是如此安排, 而《算法设计》这本书也仿效这个在一开始讲合并—查找的设计，说明这个案例确实特别经典，而且适合初学者入门。
第2章 排序
第2章和第3章着重讨论排序和查找，一眼就能看出来用的是Knuth《计算机程序设计艺术》第3卷的体系，而这也是Sedgewick精心研究的内容。
一开始讲了几个简单的排序算法，也就是插入排序和选择排序这些平方时间的排序，我觉得这几种算法练练手就可以了。另外《算法》第4版给出了排序算法的可视化，现在数据结构和算法的可视化也是相当重要的(推荐VisuAlgo：https://visualgo.net/)，数据到底如何变化用直观方式就可以学明白。
前一段时间有人在微博上问我Shell排序的一个细节问题。说实话，这些排序算法现在看得很少，能不讲就不讲，这些东西平时也不用，性能也一般。其实也失去了讲解的意义，没事看看就好了。
基础的排序我们就不谈太多，接下来我们就看看线性对数时间量级的排序算法。
2.2 归并排序，实现方式有两种：自顶向下的递归实现和自底向上的实现。归并排序看起来没什么太大的用处(因为它不是特别快)，但在外存排序里非常有用，而且它基本上是少数几个外存排序里最主流和最实用的一种了，其他排序算法基本都用不上。我所翻译的《算法设计指南》里面有个War Story讲了一点外存排序的思想。最后谈了一下排序问题的复杂度，也就是排序算法的线性对数下界，讲到这里相信大家会有一点对排序问题的本质理解了。
2.3 快速排序，快速排序大家都要讲，而《算法》第4版讲了改进。有时间的话，建议大家可以看看不同版本的标准库实现(特别是clang)，看看这些库究竟是怎么实现的。实际上，自己实现的快速排序算法性能一般不太好，特别是在处理递归调用比较多的时候(可以试试10亿个浮点数)，尾递归太多容易栈溢出。
看了标准库的实现之后，就会明白什么是理论与工程的完美结合，而快速排序是一个特别好的例子。例如这个
qsort的实现：https://opensource.apple.com//source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
2.4 优先级队列和堆堆排序。实际上优先级队列是非常有用的抽象数据类型，有一篇小论文说到荒岛上你会带什么唯一的抽象数据类型，答案就是优先级队列。
论文名：If you were lost on a desert island, what one ADT would you like to have with you? 优先级队列可以实现栈，也可以实现队列，只需要用时间为优先级即可。
优先级队列的变化还是相当多的，可以深入了解这方面的知识，例如可以参考Handbook of Data Structures and Applications。有了优先级队列之后，接着讲堆排序，这里不再多说，给一个堆排序的实现(https://opensource.apple.com/source/Libc/Libc-167/stdlib.subproj/heapsort.c.auto.html)。
2.5 这节的关键是该使用哪种排序算法，什么时候用什么排序，这个问题很重要。
排序讲到这里就结束了，最有用的就是三种：归并排序、快速排序和堆排序，讲得很简化。其实我觉得可以更极端一点，基础的排序只需要知道这两点即可：插入排序在小数据情况很快；选择排序可以过渡到堆排序。其他平方时间的排序都可以不讲了，反正用处也不是很大。
实际上，学堆排序更大的用处是为了让你了解和掌握优先级队列这种抽象数据类型。快速排序是为了让你了解随机化算法。归并排序是外存算法，尽可能少做内外存交换(但不可能完全用内存处理)。
也就是说，我们从排序这章要学一些算法思维和工程思想。
第3章 查找
排序和查找为何如此重要，Knuth在《计算机程序设计艺术》第3卷提到大多数主机的时间都在进行排序和查找，而查找对于我们来说更为常见。查找部分的内容首先从符号表开始，所谓符号表就是一个"键—值"的集合，而查找就是用键去查值。
3.2和3.3 第一种思路是最坏时间所有操作都能在对数时间内完成的树查找结构，一般要完成插入、删除和查找，它们都在可以对数时间内完成。先用二叉查找树，但是它在最坏情况下达不到对数时间而退化成链表，基本原因是不平衡也就是树太高了。为了平衡用了两种方法就是2-3树和红黑树，有的书上会讲AVL树但《算法》第4版放在习题里了。
我个人认为，红黑树其实也不用掌握，一般人知道有这么一种结构可以高效实现集合就可以了，效率就是对数时间，而且是最坏情况的保证。
3.4 不过对数时间虽然比较快，而且最坏情况有保证，但真去查找起来有时候不如散列。如何调整散列是一个比较技术性的内容。很多人有这样的误解，散列的查找在期望时间是常数时间，那全部都用散列就好了。很多语言比如Python都提供了字典，而且是常数时间，用起来很方便，好像很厉害。但最坏情况下会退化成线性时间，但是一定要有所选择，特别是最坏情况有要求。当然，还有更多高级技术，可以改进散列。
一定不能一提到散列就马上认为是常数时间特别好，要有选择地使用。而且《算法》第4版也讲了如何选择散列还是树结构。没有免费午餐(No Free Lunch)！
看起来查找部分内容不多，其实我们大家平时用的也就是这些抽象数据类型，比如C++里也就是set(红黑树实现)和unorder_set(散列实现)而已，其他语言也都有类似这样的抽象数据类型，所以用其他语言也可以看《算法》第4版，不影响对算法实质的掌握。
第4章 图
前面讲完直接跳到图算法，图算法在《算法》第4版的篇幅也不是很多，其实很多人在实际工作中也用不到特别深入的图算法，真正要用的时候又可能一筹莫展。于是就有这样的难题：到底图算法要学到什么层次，教材又该如何选择教学内容呢？
4.1 无向图，这里讲道了深度优先搜索和广度优先搜索，里面讲的最多是迷宫。迷宫到底用DFS还是BFS呢？读者不妨考虑一下。下来是连通分量。这些都是图论里的简单内容，但是能提升读者的图算法思想。随后讲了有向图、可达性和强连通分量，特别重要的就是强连通分量(SCC)算法，而这是《算法》第4版里比较难的内容了(因为没讲网络流，其实一般人也不要学网络流了，学一些基本图算法就够了)。
物理学家黄昆说道：学习知识不是越多越好、越深越好，而是应当和自己驾驭知识的能力相匹配。这句话放在算法学习特别是图算法的学习是相当合适的。
4.3 最小生成树，主要是Prim算法和Kruskal算法。特别是Kruskal算法又用到了合并—查找，这里可以看到数据结构的优化在图算法中能起到很重要的作用，提速特别明显。要注意，有些算法思想不一定今天能用到，但你的思路改进了，思想开阔了，将来就有可能用到，最差也可以感受一下算法之美。
选择一本算法书的基准是看看图的表示方法，如果不能正确使用邻接表描述图算法，那么说明作者的图算法没有入门。很多教材用邻接矩阵描述，而主流的算法设计以及分析都应该建立在邻接表上。
4.4 最短路径。这里不多说最短路径的内容了，举个例子，平时我们叫车用最短路径，如果是时长的话可以考虑最短时长路径的求解。
第5章 字符串
对很多程序员更有用的其实是字符串的处理，一般算法书讲得少，觉得似乎不是特别高端，不如动态规划炫酷，但《算法》第4版着重讲解了这部分内容。
5.1 一开始讲的可以认为是针对多键(multiple keys)或者多个数据域的排序。对于字符串来说，低位优先(LSD)可以更快地对等长的字符串来排序，而不会去用快速排序这些普适算法，这样处理字符串更快，而字符串的取值空间有限特性很重要。而不等长的可以采用高位优先(MSD)，后面进一步改进成字符串的三路快速排序，深入探讨了字符串排序。
Bentley和Sedgewick的论文Fast Algorithms for Sorting and Searching Strings可以深入研究(http://www.cs.princeton.edu/~rs/strings/paper.pdf)，阐述了Multikey Quicksort的原理并分析了性能。另外，Sedgewick的讲义Advanced Topics in Sorting(https://www.cs.princeton.edu/~rs/AlgsDS07/05AdvTopicsSorting.pdf)有关于排序的一些高级主题。
5.2 trie，也就是单词查找树。搜索框就是简单的trie，比如想输入abstract，那么依次输入a-b-s-t，先从树上走a这个分支，再走b随后走s继续走t分支，最后剩下的以abst为前缀的单词也没剩几个了，很容易找到abstract这个单词，注意这种实现需要26叉树(可用ternary search trie改进之)。trie非常有用，还有后缀树和后缀数组等内容也可以作为选学材料。
5.3 字符串的查找，所谓模式匹配，Sedgewick强调的是后面的一系列算法(当然不能绕过他老师的KMP算法)，例如Boyer-Moore算法和Rabin-Karp算法，这两种更有用而且更快。KMP强烈依赖于自我的模式，要自身重复，但很多字符串不具备这些特性，而Boyer-Moore或Rabin-Karp更适合于一般的字符串查找。
5.4 讲完上述内容就开始讨论正则表达式。又一次说明了字符串这章对实际程序员更有用，一般算法教材讲的图算法还有动态规划对于普通程序员来说，要想用好其实很难，而字符串却经常能感受到。
5.5 本章结尾讲到了数据压缩，这部分是非常好的算法应用场景。像CMU的"真实世界的算法"这门课程里讲了很多数据压缩的算法(还有纠错编码和线性规划)，也就是实际算法可以看到很多字符串的处理，又比如Huffman编码用到了优先级队列，处理数据可以用到trie还有散列，形形色色算法的应用让你亲身体验算法之大用。其实，数据压缩不是太难，自己如果可以很快实现压缩软件会有一定成就感。我讲信息论课程的时候会让学生做一般文本文件的数据压缩，看看压缩和解压的效率与常用软件如Winzip或者7zip有什么性能差异，这样能极大地提升学习兴趣。此外，文本压缩还有一些字典系列的编码(7zip的体系)，还会有更多算法与数据结构的应用，特别是散列还有滑动窗的设置，如果能实现基本的LZ77和LZ78，那么算法了解和应用又能上一个台阶。我也借鉴《算法》第4版的一些特点，让学生实现DNA序列的压缩，这样会有趣味性，也更有针对性。
CMU的15-853: Algorithms in the Real World这门课程(http://www.cs.cmu.edu/~guyb/realworld.html)非常值得一看，非常适合进阶学习。
第6章 实境
《算法》第4版前五章的内容很精炼，和其他算法书都不一样，也许称之为《数据结构与算法》更合适一点，因为讲数据结构的内容较多。
第6章就是讲真实的问题，并由此引出前面的算法和指导读者应该学习什么样的内容。在真实问题的背景下把前面的内容拿出来再讲，其实效果非常好。
典型例子是离散事件仿真(DES)，例如公交车的调度仿真要考虑某个线路何时发车。发车相当于一个"事件"，有很多车会发车但时间不同，我们不是按照固定时间间隔(例如分钟)向前逐个处理和方针，而是处理"事件"并将其放入优先级队列，只需按照事件发生时间先后取出并处理，最早出现的事件肯定最先出队，这样能够极大提升算法仿真速度。不能按时间间隔去逐个处理，这样特别慢，比如当前时间为6:30而如果下一个事件7:10出现，那么时间点直接推进到7:10即可。
语言选用
《算法》这个系列的书最开始用C语言，可能是想让他老师Knuth的书更简单容易读，另外那个年代C还是比较流行的。后来大家用C++，Sedgewick也推出了相关版本，并且也推进到Java版本。但第4版不标注语言版本直接用Java，也说明Java的热度，实际上没有提到什么语言也说明不想写别的语言版本了。
不过，现在用Python也很多而且也更接近于机器学习和数据处理，这个其实很合理，一门语言学好了能做很多事情，所以都去学Python。而Sedgewick紧跟时代，又出了专门讲Python的教材，我本来觉得第5版很可能就是Python版(假设有第5版)。因为前期的Python基础的书已经有了，程序设计的知识讲过了，后面直接用Python讲算法课而且还可以做机器学习，这也是MIT多年讲《算法导论》的首选语言，大势所趋嘛，而且实现起来方便。最关键的是，很多人不愿意用复杂的语言解决问题，现在的人越来越懒:-)而且重度依赖于机器，没事不用C和C++写程序。
为了求证这个Python版本的猜测，我邮件求证了Wayne，他说暂无
Python版本的写作计划，其原因是用Python写的代码远远慢于Python自身提供的库函数，这样起不到展示算法和数据结构效率的目的。
排版
实际上排版是《算法》第4版的一大特色，第3版用LaTeX排版，而第4版居然用InDesign排版，但是双色印刷相当精美细致。主要是公式很少，所以用了InDesign。
我邮件咨询过Wayne，这么复杂的图能用LaTeX排出来么？他的回复让我很诧异，居然是用InDesign排版，另外这些精美的插图矢量图是拿AI画的，所以融合起来用Adobe一家的产品更好，保持一致。实际上从成书效果来看，排版确实美轮美奂，非常满意。
当然也是因为《算法》第4版的公式少，实际上这本书基本不讲公式，能不用就不用，这点节约了大家的脑力。因为数学确实会给很多人带来困扰，实际上数学让人会有特别深的恐惧感。算法再加数学更让人害怕了，所以《算法》第4版用到了算法运行实况(到底如何运行，一步步告诉大家)和可视化的方法。
《算法》第4版和前3版有将近40年的传承，而第二作者Wayne为这一版本付出了相当大的心血，这点很难得(绝大多数高校教师因为要做科研所以做不到这点，而且也没有这么多精力来精心编撰教材)，而Wayne投入了很多精力放在这本书上。不过，从绘图和排版软件的选择上来说，还是比较符合这本书的目的，主要能更好服务于普通读者，一看就不是特别难，而且又是彩色印刷，所以很能吸引眼球。
Q & A
- 先修课程是什么？有一点离散数学知识就可以了，《算法导论》后面的附录基本也就够了，可以放心学《算法》第4版。
- 要学什么数学？学别的算法书，离散数学是要学的，高等数学也是要学的，概率论也是不能丢的，线性代数也得非常好才行，矩阵如果不会好多东西用不成。但《算法》第4版里基本没有什么矩阵，哈哈。当然，多学一点离散数学更好，但是要看个人能力而定。既然不能学复杂的内容，那就吸收点有用的东西让程序提升吧，一定要养成很好的品味，有好坏的算法之分，这点很重要。
- 多久能看完？不要指望很快看完。
- 应该买中文版还是英文版？英文教材和课程其实学起来还是有点难度，所以大家根据自己需要和能力范围选择购买中文版或英文版。
- 写程序的态度应该如何？尽量少写低效的算法，甚至于低效的程序，要尽量提高程序的性能。
《算法》第4版，帮助你在平常而又不平凡的程序设计里找到更多乐趣！
知识星球
