《算法》第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：visualgo.net/)，資料到底如何變化用直覺方式就可以學明白。

前一段時間有人在微網誌上問我Shell排序的一個細節問題。說實話，這些排序算法現在看得很少，能不講就不講，這些東西平時也不用，性能也一般。其實也失去了講解的意義，沒事看看就好了。

基礎的排序我們就不談太多，接下來我們就看看線性對數時間量級的排序算法。

2.2 歸并排序，實作方式有兩種：自頂向下的遞歸實作和自底向上的實作。歸并排序看起來沒什麼太大的用處(因為它不是特别快)，但在外存排序裡非常有用，而且它基本上是少數幾個外存排序裡最主流和最實用的一種了，其他排序算法基本都用不上。我所翻譯的《算法設計指南》裡面有個War Story講了一點外存排序的思想。最後談了一下排序問題的複雜度，也就是排序算法的線性對數下界，講到這裡相信大家會有一點對排序問題的本質了解了。

2.3 快速排序，快速排序大家都要講，而《算法》第4版講了改進。有時間的話，建議大家可以看看不同版本的标準庫實作(特别是clang)，看看這些庫究竟是怎麼實作的。實際上，自己實作的快速排序算法性能一般不太好，特别是在處理遞歸調用比較多的時候(可以試試10億個浮點數)，尾遞歸太多容易棧溢出。

看了标準庫的實作之後，就會明白什麼是理論與工程的完美結合，而快速排序是一個特别好的例子。例如這個

qsort

的實作：opensource.apple.com//source/xnu…

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。有了優先級隊列之後，接着講堆排序，這裡不再多說，給一個堆排序的實作(opensource.apple.com/source/Libc…)。

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可以深入研究(www.cs.princeton.edu/~rs/strings…)，闡述了Multikey Quicksort的原理并分析了性能。另外，Sedgewick的講義Advanced Topics in Sorting(www.cs.princeton.edu/~rs/AlgsDS0…)有關于排序的一些進階主題。

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這門課程(www.cs.cmu.edu/~guyb/realw…)非常值得一看，非常适合進階學習。

第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版，幫助你在平常而又不平凡的程式設計裡找到更多樂趣！

我看了一個電影說小女孩學數學壓力過大，她母親為了解開世界難題自殺了，