目前最好的算法書

這是從圖靈 2016 年發的一篇文章修改而來的标題，原先這篇文章的标題叫《如果你隻能擁有一本算法書》。沒錯，這次，我們就不遮遮掩掩了，引用了一位大學教授的書評标題「 Best algorithms textbook by far」。從市場和讀者的回報看，這也不是虛假宣傳。這篇文章的核心是一篇書評，我們依然保留，送給 2016 年還沒來得及認識圖靈的小夥伴，以及還在猶豫選擇哪本算法參考書的小夥伴。

如果關注算法圖書，你可能已經猜到我們這本書的主角了，是：《算法（第 4 版）》。

完全不誇張，《算法（第 4 版）》是目前市面上口碑、銷量、學習友好度綜合排名第一位的算法圖書。

《算法（第4版）》豆瓣中文版評分 9.4，Amazon 英文版評分 4.6，圖靈同時引入出版了中英文版，一直超級受歡迎。最近兩年，其受歡迎程度快速穩步上漲。

當然，一本書無論别人怎麼說它好，具體到你，總要去研究它是否真的适合自己的閱讀習慣和閱讀品味。那麼，這本書好在哪裡？你是否需要呢？

以下是 Amazon 高票支援的《算法（第4版）》書評，也是相對客觀的書評。我們來看看這位大學教授是如何評價這本書的。

最後，我們也在「閱讀原文」給出了圖靈算法書單，歡迎小夥伴挑到适合自己的算法書，攻克算法難題。

目前最好的算法參考書  

★★★★★ 389人覺得有用

作者：Kevin P. Murphy  （不列颠哥倫比亞大學計算機系教授）

Robert Sedgewick 和 Kevin Wayne的《算法》（第4版，由 Addison-Wesley 于 2011 年 3 月出版）是我讀過的最棒的計算機科學方面的書籍之一。它應該是所有程式員以及計算機科學專業的學生的必讀書籍——它的目标是覆寫“每個程式員都應該了解的 50 個算法”。下面我就來說說為什麼我覺得這本書是如此優秀。

1

Java源代碼  

《算法》包含了具體的源代碼（基于一個 Java 的子集），這和它的主要對手——由 Cormen、Leiserson、Rivest 和 Stein （CLRS）完成的《算法導論》（An introduction to algorithms）——非常不同。這一點非常重要，因為它意味着學生們可以使用這些代碼去解決許多真實的問題。這些算法産生了從網絡搜尋到基因組學的許多有趣和令人激動的應用，這些應用也貫穿了全書（這本書的網站上提供了所有的源代碼和資料）。

對真實代碼的一種很自然的擔心是它們可能會影響對概念的了解。但在這本書中，作者通過精心定義的抽象資料類型（隊列、背包、哈希表、樹、有向無環圖等類）賞心悅目的創造了許多既有可讀性又非常準确的實作。

使用真實代碼的另一個好處是迫使你解決一些容易被忽略卻十分重要的實作細節。例如，大家都知道并歸排序需要輔助性記憶體空間。在 CLRS 的僞代碼中，作者在他們的并歸函數内部配置設定的臨時存儲空間。但在實踐中，僅配置設定一次臨時存儲空間并将它作為一個指針傳遞給并歸函數（或是将它作為并歸排序類的一個私有成員）将會高效得多。這種重要的技巧你又可以從哪裡學到呢？

2

代碼配以詳細的語言闡釋 

除了代碼的展示之外，本書也用清晰的語言解釋了這些方法。本書非常與衆不同的一點就是包含許多詳細的例子來說明這些算法在處理真實資料時的行為和表現。（除非你真的實作了這些算法，否則是很難得到這些資料的！）

3

嚴格遵循軟體工程實踐 

這本書的另一個優點是它嚴格遵守了軟體工程的最佳實踐：先寫 API，再寫單元測試或是實作一個使用該資料結構或算法的應用（用例），最後才考慮應該如何實作這個 API。另外，本書在許多時候還讨論了同一 API 的多種實作，它們在簡潔性、速度和記憶體使用上的折中都各有不同。

對于資料結構，使用“類”是很自然的，但對于算法作者也采用了這種描述方式，特别是圖算法。這使得算法能夠進行預處理并儲存一些内部狀态，然後再為使用者提供服務。這種方式比傳統的無狀态的函數式的算法更加通用。

4

經驗性算法題練習 

這本書的每一節都有大量的練習，分為“簡單”、“提高”和“實驗”三種，它的網站提供了部分練習的解答。

除了理論之外，本書還含有許多經驗性的算法題目，這也是特色。它展示了算法的不同實作對于不同規模問題的實際運作時間，并用這些資料作為傳統理論分析的補充。

相比 CLRS，這本書的一個小優點是沒有那麼厚（約 1000 頁，而 CLRS 有1300 頁）。

5

組織良好，循序漸進 

顯然，《算法》和 CLRS 的内容有許多重疊。從書的目錄來看這一點并不明顯，是以我寫了一份更加詳細的清單來列出這本書讨論的所有問題。

全書的組織非常好，前面介紹過的内容（和代碼）會在後面得到多次應用（例如：堆 -> 優先隊列 -> 最小生成樹的 Prim 算法）。書中的話題也會越來越進階。是以讀者最好一頁一頁的按順序閱讀本書。

下面是我制作的一份書中的話題總結，這些話題從目錄上看起來并不明顯。

 關鍵話題 

第1章 基礎

1.1  礎程式設計模型

-- Java入門

-- API與各種庫

-- 二分查找（遞歸）

1.2  資料抽象

-- 面向對象基礎

-- 避免“寬”接口

1.3  背包、隊列和堆棧

-- 泛型（C++中被稱為模闆）

-- 疊代器

-- 表達式求值的Dijkstra的雙堆棧算法

-- 動态數組

-- 連結清單與指針

1.4  算法分析

-- 經驗性算法

-- 大O記法（“線性對數”的意思是O(NlogN)）

-- 随機化的算法

-- 記憶體的使用

1.5  執行個體分析：union-find算法

-- 應用：動态連通性（p、q是否是在同一個集合中？）

-- 三種實作，最後得到一種經典的算法

第2章 排序算法

2.1  初級排序算法

-- 選擇排序

-- 插入排序

-- 希爾排序

2.2  并歸排序

-- 自頂向下的并歸排序（遞歸）

-- 運作時間是NlogN的證明

-- 自底向上的并歸排序

-- 證明排序所需的比較次數的下界是NlogN

2.3  快速排序

-- 實作

-- 分析

-- 使用三向切分加快對等鍵情況的排序

-- 證明排序成本的下界是N乘以鍵的分布的熵

2.4  優先隊列

-- 堆

-- 優先隊列

-- 使用優先隊列解決得到一列數中最大的N個數的問題

-- 使用索引優先隊列實作N個有序清單的多向合并

-- 堆排序

-- 各種排序算法的比較（速度、穩定性、原地性、額外空間的使用）

-- 順序統計以及在O(N)時間内找到中位數

第3章 查找

3.1  符号表（也叫做關聯性數組）

-- 符号表與有序符号表（鍵可以被比較，是以可以得到最大和最小鍵）

-- 在一份大文檔中統計詞頻

-- 無序連結清單中的順序查找

-- 有序數組中的二分查找

3.2  二分查找樹

-- 二分查找樹的性質（父節點比左子節點大，比右子節點小）

-- get和put方法的實作，以及對其所需時間為O(logN)的分析

-- 查找最小元素、删除最小元素、删除任意元素

-- 中序周遊

3.3  平衡查找樹

-- 2-3樹和紅黑樹

3.4  哈希表

-- 哈希函數（例如，取模以及Horner法則）

-- 拉鍊法

-- 線性探測法

3.5  應用

-- 去重

-- 字典查找

-- 逆向索引

-- 檔案索引

-- 稀疏矩陣向量的乘法

第4章 圖

4.1  無向圖

-- 臨接表的表示

-- 深度優先搜尋

-- 廣度優先搜尋

-- 基于廣度優先搜尋的單點最短路徑算法

-- 基于深度優先搜尋的連通分量算法

-- 使用深度優先搜尋判斷G是否是無環的

-- 使用深度優先搜尋判斷G是否是二分的

-- Kevin Bacon遊戲（六度理論）

4.3  權重無向圖的最小生成樹

-- Prim算法

-- Kruskal算法

4.4  權重圖中的最短路徑

-- Dijkstra算法

-- 權重有向無環圖中的最短路徑

-- 排程問題的關鍵路徑算法

-- 權重有環有向圖中的最短路徑（Bellman-Ford算法與負權重邊的檢測）

-- 套彙

第5章 字元串

5.1  字元串排序

-- 鍵索引計數法（基數排序）

-- 低位優先的字元串排序

-- 高位優先的字元串排序

-- 适用于帶有重複字首字元串的三向字元串快速排序

5.2  字典查找樹

-- R向字典查找樹

-- longestPrefixOf方法（最長公共字首）

-- 三向字典查找樹（R向數組的二分查找樹表示）

5.3  子字元串查找

-- 暴力方法

-- KMP算法

-- Boyer-Moore算法

-- Rabin-Karp指紋算法

5.4  正規表達式

-- 文法

-- 使用非确定性有限狀态自動機判定字元串是否在特定的語言中

5.5  資料壓縮

-- 基礎知識

-- 遊程編碼

-- 哈夫曼壓縮算法

-- LZW壓縮算法（基于字典查找樹）

第6章 背景

6.1  基于優先隊列的事件驅動模拟

6.2  B樹

6.3  字尾數組

-- 找出最長重複子字元串

-- 字元串的索引（上下文中的關鍵字）

6.4  Ford-Fulkerson最大流量算法

-- 尋找最短增廣路徑

-- 最大二分圖比對問題向最大流量問題的歸約

-- 最大流量問題和最短路徑問題向線性規劃問題的歸約

6.5 NP完全性

END

作者：Kevin Wayne，Robert Sedgewick

譯者：謝路雲

定價：99.00元 / 英文版129.00元

• 分中文版和英文版，豆瓣 9.4 分
• 幾十年多次修訂，經久不衰的暢銷書
• 涵蓋所有程式員必須掌握的 50 種算法
• Sedgewick 之巨著，與高德納 TAOCP 一脈相承

本書作為算法領域經典的參考書，全面介紹了關于算法和資料結構的必備知識，并特别針對排序、搜尋、圖處理和字元串處理進行了論述。第 4 版具體給出了每位程式員應知應會的 50 個算法，提供了實際代碼，而且這些 Java 代碼實作采用了子產品化的程式設計風格，讀者可以友善地加以改造。本書配套網站提供了書中内容的摘要及更多的代碼實作、測試資料、練習、教學課件等資源。

中文版一鍵購買

英文版一鍵購買

☟ 「閱讀原文」圖靈算法書單