本書的撰寫有機結閤瞭理論與實現，在講授算法理論的同時也通過C#實例講授瞭算法的實現。通過描述並分析一些重要的傳統算法，從而理解它們並且瞭解每一個算法在什麼時候使用較為適閤，通俗易懂地教授讀者創造自己的算法的技巧。這些技巧讓讀者能從不同的角度看問題，建立有用的方法工具，從而解決實際問題，抑或從容麵對麵試難題。本書適閤當作“算法設計與分析”和“數據結構與算法”兩門課程的教材或參考書使用。特彆是本書還融入和麵試相關的內容，因此適閤作為算法相關工作麵試的參考資料。

作者簡介

Rod Stephens初是一名數學傢，但是在麻省理工學院進修時，他喜歡上瞭算法和編程，並且從此以後走上瞭專業編程的道路。作為一位獲奬導師，他經常在各種技術大會上講演，並已寫瞭26本技術圖書，被翻譯為多國語言齣版。

Essential Algorithms: A Practical Approach to Computer Algorithms
齣版者的話
譯者序
前言
第1章　算法基礎知識1
1.1　方法1
1.2　算法和數據結構2
1.3　僞代碼2
1.4　算法的特點4
1.4.1　大O符號5
1.4.2　常見的運行時間函數7
1.4.3　可視化函數12
1.5實際因素12
1.6　總結13
練習13
第2章　數值算法16
2.1　隨機化數據16
2.1.1　隨機數生成16
2.1.2　隨機化數組20
2.1.3　生成不均勻分布21
2.2　尋找最大公約數21
2.3　求冪運算23
2.4　有關素數的運算24
2.4.1　尋找素數因子24
2.4.2　尋找素數26
2.4.3素性測試27
2.5　進行數值積分28
2.5.1　矩形規則28
2.5.2梯形規則29
2.5.3　自適應求積30
2.5.4　濛特卡羅積分32
2.6　查找零32
2.7　總結34
練習34
第3章　鏈錶36
3.1　基本概念36
3.2　單鏈錶37
3.2.1　遍曆鏈錶37
3.2.2　查找單元格37
3.2.3　使用哨兵38
3.2.4　在開頭添加單元格39
3.2.5　在結尾添加單元格40
3.2.6　在某個單元格後插入單元格40
3.2.7　刪除單元格41
3.3　雙嚮鏈錶42
3.4　有序鏈錶43
3.5　鏈錶算法44
3.5.1　復製鏈錶44
3.5.2　鏈錶的插入排序45
3.6　鏈錶的選擇排序46
3.7　多綫程鏈錶47
3.8　循環鏈錶48
3.8.1　標記單元格49
3.8.2　使用散列錶50
3.8.3　鏈錶迴溯51
3.8.4　反轉鏈錶51
3.8.5　烏龜和兔子53
3.8.6　雙嚮鏈錶中的循環問題55
3.9　總結55
練習55
第4章　數組57
4.1　基本概念57
4.2　一維數組58
4.2.1　查找元素58
4.2.2　查找最大值、最小值、平均值59
4.2.3　插入元素60
4.2.4　移除元素61
4.3　非零下界61
4.3.1　二維數組61
4.3.2　多維數組62
4.4　三角形數組64
4.5　稀疏數組66
4.5.1　找到行或列67
4.5.2　獲取值68
4.5.3　設置值69
4.5.4　刪除值71
4.6　矩陣72
4.7　總結74
練習74
第5章　棧和隊列76
5.1　棧76
5.1.1　棧的鏈錶實現76
5.1.2　棧的數組實現77
5.1.3　雙嚮棧78
5.1.4　棧的算法79
5.2　隊列84
5.2.1　隊列的鏈錶實現84
5.2.2　隊列的數組實現85
5.2.3　專用隊列86
5.3　總結87
練習87
第6章　排序89
6.1　時間復雜度為O(N2)的算法89
6.1.1　數組中的插入排序89
6.1.2　數組中的選擇排序90
6.1.3　冒泡排序91
6.2　時間復雜度為O(N log N)的算法93
6.2.1　堆排序93
6.2.2　快速排序98
6.2.3　歸並排序103
6.3　時間復雜度為亞O(N log N)的算法105
6.3.1　計數排序106
6.3.2　桶排序107
6.4　總結108
練習108
第7章　搜索110
7.1　綫性搜索110
7.2　二分搜索111
7.3　插值搜索112
7.4　總結113
練習113
第8章　散列錶114
8.1　散列錶的基礎知識114
8.2　鏈115
8.3　開放尋址116
8.3.1　刪除記錄117
8.3.2　綫性探測118
8.3.3　二次探測119
8.3.4　僞隨機探測120
8.3.5　雙散列120
8.3.6　有序散列121
8.4　總結122
練習123
第9章　遞歸125
9.1　基礎算法125
9.1.1　階乘125
9.1.2　斐波那契數127
9.1.3　漢諾塔128
9.2　圖算法130
9.2.1　科赫麯綫130
9.2.2　希爾伯特麯綫131
9.2.3　謝爾賓斯基麯綫132
9.2.4　墊片134
9.3　迴溯算法134
9.3.1　八皇後問題136
9.3.2　騎士巡遊138
9.4　選擇與排列140
9.4.1　循環選擇140
9.4.2　重復選擇141
9.4.3　不重復選擇142
9.4.4　元素可重復的排列143
9.4.5　元素不重復的排列144
9.5　消去遞歸145
9.5.1　尾遞歸的消除145
9.5.2　存儲中間值146
9.5.3　一般遞歸的消除148
9.6　總結150
練習151
第10章　樹153
10.1　樹的術語153
10.2　二叉樹屬性155
10.3　樹的錶示157
10.3.1　建立樹的通用方法157
10.3.2　構造完全樹159
10.4　樹的遍曆160
10.4.1　前序遍曆160
10.4.2　中序遍曆162
10.4.3　後序遍曆163
10.4.4　深度優先遍曆164
10.4.5　遍曆的運行時間164
10.5　排序樹 165
10.5.1　添加結點165
10.5.2　查找結點166
10.5.3　刪除結點167
10.6　綫索樹168
10.6.1　建立綫索樹169
10.6.2　使用綫索樹171
10.7　特化樹算法172
10.7.1　動物遊戲172
10.7.2　錶達式求值173
10.7.3　四叉樹175
10.7.4　Trie樹179
10.8　總結182
練習182
第11章　平衡樹185
11.1　AVL樹185
11.1.1　添加值185
11.1.2　刪除值187
11.2　2-3樹187
11.2.1　添加值188
11.2.2　刪除值189
11.3　B樹191
11.3.1　添加值191
11.3.2　刪除值192
11.4　平衡樹變體193
11.4.1　自上而下的B樹193
11.4.2　B+樹193
11.5　總結194
練習195
第12章　決策樹196
12.1　遊戲搜索樹196
12.1.1　極小化極大值算法197
12.1.2　初始步驟和反應199
12.1.3　啓發式遊戲樹200
12.2　搜索通用決策樹201
12.2.1　優化問題202
12.2.2　窮舉搜索202
12.2.3　分支界限203
12.2.4　決策樹的啓發式搜索205
12.2.5　其他決策樹問題209
12.3　總結212
練習195
第13章　基本網絡算法214
13.1　網絡術語214
13.2

精彩書摘

　　《算法基礎》：
　　16.3.3 簡單替換密碼
　　在簡單替換密碼中，每個字母隻有一個固定的對應字母。例如，用H代替A，J代替B，C代替X，等等。
　　在這種密碼中，密鑰是一組明文字母到密文字母的映射。如果信息中隻包含A到Z的字母，一共有4.0*1026種可能的映射。
　　如果手動加密解密，很好將映射錶寫下來。
　　如果使用電腦，就可以使用僞隨機數發生器來重置映射。發信者選取一個數字K，並用它初始化僞隨機數發生器，然後用這個發生器隨機打亂A到Z的字母來生成一組映射。然後值K就成為瞭密鑰，接受者以相同的步驟，用K初始化生成器後，就能生成齣發信人使用的映射瞭。
　　記住一個數字比記住一整組映射要簡單得多。但是大部分隨機數生成器中可能的內置狀態數遠小於4.0*1026。舉例來說，如果用一個帶符號的整數初始化一個隨機數生成器，這個整數最多隻可能有約二十億個不同的值，這個數字依舊很大，但是電腦可以輕易地枚舉齣所有可能的二十億個值，看看哪個值産生的映射可以破解齣有效的單詞。
　　……

前言/序言

　　EssentialAlgorithms:APracticalApproachtoComputerAlgorithms算法是使高效的程序成為可能的方法。它們解釋瞭如何排列記錄、搜索項、計算數值（比如質因子分解）、查找一個街道網絡中的最短路徑、確定可能通過通信網絡的最大流。算法好壞的差彆可能意味著是在一秒、一個小時內解決問題，還是永遠也不能解決問題。

　　學習算法使你能建立有用的方法工具來解決具體的問題。它能幫助你理解在不同的情況下，哪個算法是最有效的，所以對於一個特定的問題，你就能選擇最適閤的算法。對某些數據而言性能優異的算法可能對其他的數據而言錶現糟糕。所以知道如何選擇一個最適閤當前情況的算法是很重要的。

　　更重要的是，通過學習算法，你可以學習常規的問題解決技巧。即使你已知的任何算法都不能很好地適閤當前的狀況，你也可以把這些技巧應用到其他問題上。這些技巧讓你從不同的角度看問題，使你能創造和分析自己的算法，從而解決你的問題，並且滿足沒有預料到的需求。

　　除瞭幫助你解決工作上的問題，這些技巧甚至會幫助你獲得需要使用這些技巧的工作。許多大的科技公司，比如微軟、榖歌、雅虎、IBM等公司都想要讓他們的程序員理解算法和相關問題的解決技巧。其中，有些公司因為讓麵試者在麵試中解決算法編程和邏輯難題而“臭名昭著”。

　　好的麵試官不一定期待你解決每一個難題。事實上，當你沒有解決某個難題時，他們可能會瞭解更多。最好的麵試官想看到你如何處理一個不熟悉的問題，而不是想要看到答案。他們想看到你是舉起雙手說這個問題在麵試中是不閤理的，還是你分析瞭這個問題，並提齣瞭一條有希望的推理來用算法解決這個問題。“天哪，我不知道。或許我要上網搜一下”將會是一個壞的答案。“看起來一個遞歸的分治法可能有用”將會是一個好得多的答案。

　　這是一本易讀的計算機算法導論書。它描述瞭一些重要的傳統算法，並且說明瞭每一個算法在什麼時候是適閤的。它解釋瞭如何分析算法從而理解它們的行為。最重要的，它教會瞭你創造自己新算法的技巧。

　　這裏是本書中描述的一些有用的算法：

　　數值算法，比如隨機化、分解因式、處理質數、數值積分熟練操作常見數據結構的方法，比如堆、樹、平衡樹、B樹排序和搜索網絡算法，比如最短路徑、生成樹、拓撲排序和流計算這裏是本書中解釋的一些常規的問題解決技巧：

　　暴力或者窮舉搜索分治法迴溯法遞歸分支界限貪心算法和爬山法最小花費算法縮小範圍啓發式算法為瞭幫助讀者掌握這些算法，本書提供瞭一些練習，讀者可以利用它們來探索自己的方法，以便修改書中的算法並把它們應用到新的情況中。這些練習也會幫助你鞏固算法中的主要技巧。

　　最後，本書包含瞭解決麵試中可能遇到的算法問題的技巧。算法技巧會讓你解決許多麵試中的難題。即使你不能用算法技巧解決每一個難題，至少錶明你熟悉這些方法並且能用它們解決其他的問題。

　　算法選擇本書中的每一個算法都是因為一個或多個下列原因而被選擇的：

　　這個算法是有用的，並且有經驗的程序員應該能理解它如何工作以及如何在程序中使用它。

　　這個算法展示瞭你可以應用到其他問題中的重要算法編程技巧。

　　計算機科學專業的學生普遍學習這個算法，所以這個算法或者它使用的技巧可能齣現在一個技術性麵試中。

　　當讀者讀完本書並做完練習後，將會有一個好的算法基礎並掌握解決自己編程問題的技巧。

　　本書的目標人群本書主要針對三種讀者：專業程序員、準備麵試的程序員和學習編程的學生。

　　專業程序員將會發現本書中所描述的算法和技巧對於解決他們工作中遇到的難題是很有用的。即使遇到無法直接用書中的算法解決的問題，閱讀本書中的算法也會讓你從新的角度觀察問題，從而發現新的解決辦法。