前言

✤ 演算法有用嗎

「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++ 標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如向量（vector）、佇列（queue）、集合（set）也都實現好了。日常工作中了解如何使用這些函數庫似乎就足夠了。

但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。

讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。

✤ 最小可用ID，演算法的威力

這道題目來自Richard Bird 所著書中的第1章[1]。現代社會中，有很多服務依賴一種稱為ID的概念。例如身份證就是一種ID，銀行帳戶也是一種ID，電話號碼本質上也是一種ID。假設我們使用非負整數作為某個系統的ID，所有使用者都由一個ID唯一確定。任何時間，這個系統中的有些ID處於使用中的狀態，有些ID則可以分配給新使用者。現在的問題是，怎樣才能找到最小的可分配ID呢？例如下面是目前正在使用的ID：

[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]

最小的可分配ID，也就是不在這個清單中的最小非負整數，即10。

有些程式語言內建了這一線性尋找的實現，例如Python。我們可以直接將這一解法翻譯成下面的程式：

def brute_force(lst):

i = 0

while True:

if i not in lst:

return i

i = i + 1

但是這道題目僅是看上去簡單。在儲存了幾百萬個ID的大型系統中，這個方法的效能很差。對於一個長度為n的ID清單，它需要O(n2 )的時間才能找到最小的可分配ID。在我的電腦上（雙核心2.10 GHz處理器，2 GB憶體），使用這一方法的C語言程式平均要5.4 s才能在10萬個ID 找到答案。當ID的數量上升到100萬時，平均用時則長達8min。

改進一

改進這一解法的關鍵基於這一事實：對於任何n個非負整數x1 , x2 , •••, xn，如果存在小於n的可用整數，必然存在某個xi不在[0, n) 範圍內。否則這些整數一定是0, 1, •••, n −1 的某個排列，這種情況下，最小的可用整數是n。於是我們有以下結論：

minf ree(x1 , x2 , •••, xn) 至n (1)

根據這一結論，我們可以用一個長度為n + 1 的陣列，來標記區間[0, n]內的某個整數是否可用：

其中第2 行將標示陣列中的所有值初始化為False，這一步驟需要O(n) 的時間。接著我們檢查A中的所有元素，只要小於n，就將對應的標記置為True，這一過程也需要O(n)的時間。最後我們線性尋找標示陣列中第一個值為False的位置。整個演算法的效能是線性時間O(n)。

前言

✤ 演算法有用嗎

「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++ 標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如向量（vector）、佇列（queue）、集合（set）也都實現好了。日常工作中了解如何使用這些函數庫似乎就足夠了。

但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。

讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。 ...

前言
第一部分 樹
第1章 二叉搜尋樹：資料結構中的“hello world”
1.1 定義.
1.2 資料組織
1.3 插入
1.4 檢查.
1.5 搜索
1.6 刪除.
1.7 隨機建置二叉搜尋樹
第2章 插入排序的進化.
2.1 簡介
2.2 插入
2.3 改進一：二分尋找
2.4 改進二：使用鏈結串列
2.5 使用二叉搜尋樹的最後改進
2.6 小結
第3章 並不複雜的紅黑樹
3.1 紅黑樹的定義
3.2 插入
3.3 刪除
3.4 指令式的紅黑樹演算法
3.5 小結
第4章 AVL 樹
4.1 AVL 樹的定義
4.2 插入
4.3 刪除
4.4 AVL 樹的指令式演算法
4.5 小結.
第5章 基數樹：Trie 和Patricia
5.1 整數Trie
5.2 整數Patricia
5.3 字元Trie
5.4 字元Patricia
5.5 Trie 和Patricia 的應用
5.6 小結
第6章 副檔名樹
6.1 副檔名Trie
6.2 副檔名樹
6.3 副檔名樹的應用
6.4 小結
第7章 B樹.
7.1 插入
7.2 刪除
7.3 搜索
7.4 小結

第二部分 堆
第8章 二叉堆積
8.1 用陣列實現隱式二叉堆積
8.2 左偏堆積和skew 堆積：顯性的二叉堆積
8.3 延伸堆積
8.4 小結
第9章 從吃葡萄到世界盃：選擇排序的進化
9.1 尋找最小元素
9.2 細微改進.
9.3 本質改進
9.4 小結
第10章 二項式堆積、費氏堆積和配對堆積
10.1 二項式堆積
10.2 費氏堆積
10.3 配對堆積
10.4 小結

第三部分 佇列和序列
第11章 並不簡單的佇列
11.1 單向鏈結串列和循環緩衝區實現的佇列
11.2 純函數式實現.
11.3 小改進：平衡佇列.
11.4 進一步改進：即時佇列
11.5 惰性即時佇列
11.6 小結
第12章 序列：最後一塊磚
12.1 二叉隨機存取列表
12.2 二叉隨機存取列表的數值表示
12.3 指令式雙陣列清單
12.4 可連接列表
12.5 手指樹
12.6 小結

第四部分 排序和搜索
13.1 快速排序
13.2 快速排序的效能分析
13.3 工程實作中的改進
13.4 針對最差情況的工程實作
13.5 其他工程實作
13.6 其他
13.7 歸併排序
13.8 原地歸併排序
13.9 自然歸併排序
13.10 自底向上歸併排序.
13.11 平行處理
13.12 小結
第14章 搜索
14.1 序列搜索
14.2 解的搜索.
14.3 小結8
附錄列表
參考文獻
索引

前言
第一部分 樹
第1章 二叉搜尋樹：資料結構中的“hello world”
1.1 定義.
1.2 資料組織
1.3 插入
1.4 檢查.
1.5 搜索
1.6 刪除.
1.7 隨機建置二叉搜尋樹
第2章 插入排序的進化.
2.1 簡介
2.2 插入
2.3 改進一：二分尋找
2.4 改進二：使用鏈結串列
2.5 使用二叉搜尋樹的最後改進
2.6 小結
第3章 並不複雜的紅黑樹
3.1 紅黑樹的定義
3.2 插入
3.3 刪除
3.4 指令式的紅黑樹演算法
3.5 小結
第4章 AVL 樹
4.1 AVL 樹的定義
4.2 插入
4.3 刪除
4.4 AVL 樹的...