前言
✤ 演算法有用嗎
「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++ 標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如向量（vector）、佇列（queue）、集合（set）也都實現好了。日常工作中了解如何使用這些函數庫似乎就足夠了。
但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。
讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。
✤ 最小可用ID，演算法的威力
這道題目來自Richard Bird
所著書中的第1章[1]。現代社會中，有很多服務依賴一種稱為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)
✤ 小結
回顧前面兩個有趣的例題，暴力解法都捉襟見肘。對於第一題，暴力解法尚能解決較短的列表，而在第二題中暴力解法根本行不通。
第一個實例展示了演算法的力量，第二個實例展示了資料結構的重要性。有很多有趣的題目在電腦發明之前很難解決，但是透過程式設計和電腦，可以用和傳統方式完全不同的方法找到答案。相對於中小學數學課上所學的方法，這樣的方法並沒有被普遍教授。
雖然優秀的演算法、資料結構和數學書汗牛充棟，但是對程序式解法和函數式解法進行對比的卻寥寥無幾。從上面的實例中可以看到，有時函數式解法十分簡潔，並且很接近我們在數學課上所熟悉的思考方式。
本書力圖同時介紹指令式和函數式的演算法和資料結構。（Okasaki 的著作[3]中有很多函數式資料結構可供進一步參考，關於指令式的內容可以參考一些經典書[4] 以及維基百科。）本書的範例程式使用了多種程式語言，包含C、C++、Python、Haskell 和Lisp 方言Scheme， 讀者可以從https://github.com/liuxinyu95/AlgoXY
上下載本書的全部範例程式。為了讓具有不同背景的讀者都容易閱讀，所有演算法都提供虛擬程式碼和數學函數描述。
由於時間倉促，書中難免存在錯誤，歡迎讀者們和專家批評指正，提供意見和回饋。
本書作者電子電子郵件：
[email protected]。
✤ 內容組織
在接下來的章節中，我們將先介紹基本的資料結構，此後的一些演算法都會用到它們。第一部分首先介紹資料結構中的"hello world"--二元搜尋樹，接下來說明如何解決二元樹的平衡問題。然後我們將介紹更多有趣的樹，其中Trie、Patricia 和後綴樹可以用於文字處理，而B樹則廣泛應用於檔案系統和資料庫。
第二部分介紹堆積的相關內容。我們列出一個抽象堆積的定義，然後介紹如何使用陣列和各種二元樹實現二元堆積（binary heap），接著擴充到其他的堆積，包含二項式堆積、費氏堆積和配對堆積（pairing heap）。
陣列和佇列通常被認為是簡單的資料結構，但我們將在第三部分看到，它們實現起來並不容易。
作為基本的排序演算法，我們將介紹指令式和函數式的插入排序、快速排序和歸併排序等演算法。第四部分介紹尋找和搜索的相關內容，除了基本演算法，還會介紹諸如KMP這樣的文字比對演算法。
附錄介紹關於鏈結串列的基本內容。
