算法(第4版)（簡體書）

《算法(第4版)》作為算法領域經典的參考書，全面介紹了關于算法和數據結構的必備知識，并特別針對排序、搜索、圖處理和字符串處理進行了論述。第4版具體給出了每位程序員應知應會的50個算法，提供了實際代碼，而且這些Java代碼實現采用了模塊化的編程風格，讀者可以方便地加以改造。配套網站提供了《算法(第4版)》內容的摘要及更多的代碼實現、測試數據、練習、教學課件等資源。《算法(第4版)》適合用做大學教材或從業者的參考書。《算法（第4版）》全面講述算法和數據結構的必備知識，具有以下幾大特色。1、算法領域的經典參考書：Sedgewick暢銷著作的新版，反映了經過幾十年演化而成的算法核心知識體系2、內容全面：全面論述排序、搜索、圖處理和字符串處理的算法和數據結構，涵蓋每位程序員應知應會的50種算法3、全新修訂的代碼：全新的Java實現代碼，採用模塊化的編程風格，所有代碼均可供讀者使用4、與實際應用相結合：在重要的科學、工程和商業應用環境下探討算法，給出了算法的實際代碼，而非同類著作常用的偽代碼5、富於智力趣味性：簡明扼要的內容，用豐富的視覺元素展示的示例，精心設計的代碼，詳盡的歷史和科學背景知識，各種難度的練習，這一切都將使讀者手不釋卷6、科學的方法：用合適的數學模型討論算法性能，這些模型是在真實環境中得到驗證的7、與網絡相結合：配套網站algs4.cs.princeton.edu提供了本書內容的摘要及相關的代碼、測試數據、編程練習、教學課件等資源

Robert Sedgewick，斯坦福大學博士，導師為Donald E. Knuth，從1985年開始一直擔任普林斯頓大學計算機科學系教授，曾任該系主任，也是Adobe Systems公司董事會成員，曾在Xerox PARC、國防分析研究所（ Institute for Defense Analyses）和法國國家信息與自動化研究所（INRIA）從事研究工作。他的研究方向包括解析組合學、數據結構和算法的分析與設計、程序可視化等。

Kevin Wayne，康奈爾大學博士，普林斯頓大學計算機科學系高級講師，研究方向包括算法的設計、分析和實現，特別是圖和離散優化。

Sedgewick之巨著，與高德納TAOCP一脈相承
幾十年多次修訂，經久不衰的暢銷書
涵蓋所有程序員必須掌握的50種算法

本書力圖研究當今最重要的計算機算法並將一些最基礎的技能傳授給廣大求知者。它適合用做計算機科學進階教材，面向已經熟悉了計算機系統並掌握了基本編程技能的學生。本書也可用於自學，或是作為開發人員的參考手冊，因為書中實現了許多實用算法並詳盡分析了它們的性能特點和用途。這本書取材廣泛，很適合作為該領域的入門教材。
算法和數據結構的學習是所有計算機科學教學計劃的基礎，但它並不只是對程序員和計算機系的學生有用。任何計算機使用者都希望計算機能運行得更快一些或是能解決更大規模的問題。本書中的算法代表了近50年來的大量優秀研究成果，是人們工作中必備的知識。從物理中的N體模擬問題到分子生物學中的基因序列問題，我們描述的基本方法對科學研究而言已經必不可少；從建築建模系統到模擬飛行器，這些算法已經成為工程領域極其重要的工具；從數據庫系統到互聯網搜索引擎，算法已成為現代軟件系統中不可或缺的一部分。這僅是幾個例子而已，隨著計算機應用領域的不斷擴張，這些基礎方法的影響也會不斷擴大。
在開始學習這些基礎算法之前，我們先要熟悉全書中都將會用到的棧、隊列等低級抽象的數據類型。然後依次研究排序、搜索、圖和字符串方面的基礎算法。最後一章將會從宏觀角度總結全書的內容。
獨特之處
本書致力於研究有實用價值的算法。書中講解了多種算法和數據結構，並提供了大量相關的信息，讀者應該能有信心在各種計算環境下實現、調試並應用它們。本書的特點涉及以下幾個方面。算法書中均有算法的完整實現，並討論了程序在多個樣例上的運行狀況。書中的代碼都是可以運行的程序而非偽代碼，因此非常便於投入使用。書中程序是用Java語言編寫的，但其編程風格方便讀者使用其他現代編程語言重用其中的大部分代碼來實現相同算法。
數據類型
我們在數據抽像上採用了現代編程風格，將數據結構和算法封裝在了一起。
應用
每一章都會給出所述算法起到關鍵作用的應用場景。這些場景多種多樣，包括物理模擬與分子生物學、計算機與系統工程學，以及我們熟悉的數據壓縮和網絡搜索等。
學術性
我們非常重視使用數學模型來描述算法的性能。我們用模型預測算法的性能，然後在真實的環境中運行程序來驗證預測。
廣度
本書討論了基本的抽像數據類型、排序算法、搜索算法、圖及字符串處理。我們在算法的討論中研究數據結構、算法設計範式、歸納法和解題模型。這將涵蓋20世紀60年代以來的經典方法以及近年來產生的新方法。
我們的主要目標是將今天最重要的實用算法介紹給盡可能廣泛的群體。這些算法一般都十分巧妙奇特，20行左右的代碼就足以表達。它們展現出的問題解決能力令人嘆為觀止。沒有它們，創造計算智能、解決科學問題、開發商業軟件都是不可能的。
本書網站
本書的一個亮點是它的配套網站algs4.cs.princeton.edu。這一網站面向教師、學生和專業人士，免費提供關於算法和數據結構的豐富資料。
一份在線大綱包含了本書內容的結構並提供了鏈接，瀏覽起來十分方便。
全部實現代碼書中所有的代碼均可以在這裡找到，且其形式適合用於程序開發。此外，還包括算法的其他實現，例如高級的實現、書中提及的改進的實現、部分習題的答案以及多個應用場景的客戶端代碼。我們的重點是用真實的應用環境來測試算法。
習題與答案網站還提供了一些附加的選擇題（只需要一次單擊便可獲取答案）、很多算法應用的例子、編程練習和答案以及一些有挑戰性的難題。
動態可視化書是死的，但網站是活的，在這裡我們充分利用圖形類演示了算法的應用效果。課程資料網站包含和本書及網上內容對應的一整套幻燈片，以及一系列編程作業、核對錶、測試數據和備課手冊。
相關資料鏈接網站包含大量的鏈接，提供算法應用的更多背景知識以及學習算法的其他資源。我們希望這個站點和本書互為補充。一般來說，建議讀者在第一次學習某種算法或是希望獲得整體概念時看書，並把網站作為編程時的參考或是在線查找更多信息的起點。
作為教材
本書為計算機科學專業進階的教材，涵蓋了這門學科的核心內容，並能讓學生充分鍛煉編程、定量推理和解決問題等方面的能力。一般來說，此前學過一門計算機方面的先導課程就足矣，只要熟悉一門現代編程語言並熟知現代計算機系統，就都能夠閱讀本書。
雖然本書使用Java實現算法和數據結構，但其代碼風格使得熟悉其他現代編程語言的人也能看懂。我們充分利用了Java的抽象性（包括泛型），但不會依賴這門語言的獨門特性。書中涉及的多數數學知識都有完整的講解（少數會有延伸閱讀），因此閱讀本書並不需要準備太多數學知識，不過有一定的數學基礎當然更好。應用場景都來自其他學科的基礎內容，同樣也在書中有完整介紹。
本書涉及的內容是任何準備主修計算機科學、電氣工程、運籌學等專業的學生應了解的基礎知識，並且對所有對科學、數學或工程學感興趣的學生也十分有價值。
背景介紹
這本書意在接續我們的一本基礎教材《Java程序設計：一種跨學科的方法》，那本書對計算機領域做了概括性介紹。這兩本書合起來可用做兩到三個學期的計算機科學入門課程教材，為所有學生在自然科學、工程學和社會科學中解決計算問題提供必備的基礎知識。
本書大部分內容來自Sedgewick的算法系列圖書。本質上，本書和該系列的第1版和第2版最接近，但還包含了作者多年教學和學習的經驗。Sedgewick的《C算法（第3版）》、《C++算法（第3版）》、《Java算法（第3版）》更適合用做參考書或是高級課程的教材，而本書則是專門為大學一、二年級學生設計的一學期教材，也是最新的基礎入門書或從業者的參考書。
致謝
本書的編寫花了近40年時間，因此想要一一列出所有參與人是不可能的。本書的前幾版一共列出了好幾十人，其中包括（按字母順序）Andrew Appel、Trina Avery、Marc Brown、Lyn Dupré、PhilippeFlajolet、Tom Freeman、Dave Hanson、Janet Incerpi、Mike Schidlowsky、Steve Summit和Chris VanWyk。我要感謝他們所有人，儘管其中有些人的貢獻要追溯到幾十年前。至於第4版，我們要感謝試用了本書樣稿的普林斯頓及其他院校的數百名學生，以及通過本書網站發表意見和指出錯誤的世界各地的讀者。
我們還要感謝普林斯頓大學對於高質量教學的堅定支持，這是本書得以面世的基礎。Peter Gordon幾乎從本書寫作之初就提出了很多有用的建議，這一版奉行的“歸本溯源”的指導思想也是他最早提出的。關於第4版，我們要感謝Barbara Wood認真又專業的編輯工作，Julie Nahil對生產過程的管理，以及Pearson出版公司中為本書的付梓和營銷辛勤工作的朋友。所有人都在積極地追趕進度，而本書的質量並沒有受到絲毫影響。

第1章基礎
1.1基礎編程模型
1.1.1 Java程序的基本結構
1.1.2原始數據類型與表達式
1.1.3語句
1.1.4簡便記法
1.1.5數組
1.1.6靜態方法
1.1.7 API
1.1. 8字符串
1.1.9輸入輸出
1.1.10二分查找
1.1.11展望
1.2數據抽象
1.2.1使用抽像數據類型
1.2.2抽像數據類型舉例
1.2.3抽像數據類型的實現
1.2.4更多抽像數據類型的實現
1.2.5數據類型的設計
1.3背包、隊列和棧
1.3.1 API
1.3.2集合類數據類型的實現
1.3.3鍊錶
1.3.4綜述
1.4算法分析
1.4.1科學方法
1.4.2觀察
1.4. 3數學模型
1.4.4增長數量級的分類
1.4.5設計更快的算法
1.4.6倍率實驗
1.4.7注意事項
1.4.8處理對於輸入的依賴
1.4.9內存
1.4.10展望
1.5案例研究：union-find算法
1.5.1動態連通性
1.5.2實現
1.5.3展望

第2章排序
2.1初級排序算法
2.1.1遊戲規則
2.1.2選擇排序
2.1.3插入排序
2.1.4排序算法的可視化
2.1.5比較兩種排序算法
2.1.6希爾排序
2.2歸併排序
2.2.1原地歸併的抽象方法
2.2.2自頂向下的歸併排序
2.2.3自底向上的歸併排序
2.2.4排序算法的複雜度
2.3快速排序
2.3.1基本算法
2.3.2性能特點
2.3.3算法改進
2.4優先隊列
2.4.1 API
2.4.2初級實現
2.4.3堆的定義
2.4.4堆的算法
2.4.5堆排序
2.5應用
2.5.1將各種數據排序
2.5.2我應該使用哪種排序算法
2.5.3問題的歸約
2.5.4排序應用一覽

第3章查找
3.1符號表
3.1.1 API
3.1.2有序符號表
3.1.3用例舉例
3.1.4無序鍊錶中的順序查找
3.1.5有序數組中的二分查找
3.1.6對二分查找的分析
3.1.7預覽
3.2二叉查找樹
3.2.1基本實現
3.2.2分析
3.2.3有序性相關的方法與刪除操作
3.3平衡查找樹
3.3.1 2-3查找樹
3.3.2紅黑二叉查找樹
3.3.3實現
3.3.4刪除操作
3.3.5紅黑樹的性質
3.4散列表
3.4.1散列函數
3.4.2基於拉鍊法的散列表
3.4.3基於線性探測法的散列表
3.4.4調整數組大小
3.4.5內存使用
3.5應用
3.5.1我應該使用符號表的哪種實現
3.5.2集合的API
3.5.3字典類用例
3.5.4索引類用例
3.5.5稀疏向量

第4章圖
4.1無向圖
4.1.1術語表
4.1.2表示無向圖的數據類型
4.1.3深度優先搜索
4.1.4尋找路徑
4.1.5廣度優先搜索
4.1.6連通分量
4.1.7符號圖
4.1.8總結
4.2有向圖
4.2.1術語
4.2.2有向圖的數據類型
4.2.3有向圖中的可達性
4.2.4環和有向無環圖
4.2.5有向圖中的強連通性
4.2.6總結
4.3最小生成樹
4.3.1原理
4.3.2加權無向圖的數據類型
4.3.3最小生成樹的API和測試用例
4.3.4 Prim算法
4.3.5 Prim算法的即時實現
4.3 .6 Kruskal算法
4.3.7展望
4.4最短路徑
4.4.1最短路徑的性質
4.4.2加權有向圖的數據結構
4.4.3最短路徑算法的理論基礎
4.4.4 Dijkstra算法
4.4.5無環加權有向圖中的最短路徑算法
4.4.6一般加權有向圖中的最短路徑問題
4.4.7 展望

第5章字符串
5.1字符串排序
5.1.1鍵索引計數法
5.1.2低位優先的字符串排序
5.1.3高位優先的字符串排序
5.1.4三向字符串快速排序
5.1.5字符串排序算法的選擇
5.2單詞查找樹
5.2.1單詞查找樹
5.2.2單詞查找樹的性質
5.2.3三向單詞查找樹
5.2.4三向單詞查找樹的性質
5.2.5應該使用字符串符號表的哪種實現
5.3子字符串查找
5.3.1歷史簡介
5.3.2暴力子字符串查找算法
5.3.3 Knuth-Morris-Pratt子字符串查找算法
5.3.4 Boyer-Moore字符串查找算法
5.3.5 Rabin-Karp指紋字符串查找算法
5.3.6總結
5.4正則表達式
5.4.1使用正則表達式描述模式
5.4.2縮略寫法
5.4.3正則表達式的實際應用
5.4.4非確定有限狀態自動機
5.4.5模擬NFA的運行
5.4.6構造與正則表達式對應的
5.5數據壓縮
5.5.1遊戲規則
5.5.2讀寫二進制數據
5.5.3局限
5.5.4熱身運動：基因組
5.5.5遊程編碼
5.5.6霍夫曼壓縮

第6章背景
索引