前十個是來自圣經(jīng)的十大算法：

發(fā)起人的描述：《來自圣經(jīng)的證明》收集了數(shù)十個簡潔而優(yōu)雅的數(shù)學證明，迅速贏得了大批數(shù)學愛好者的追捧。如果還有一本《來自圣經(jīng)的算法》，哪些算法會列入其中呢？

***名：Union-find

嚴格地說，并查集是一種數(shù)據(jù)結構，它專門用來處理集合的合并操作和查詢操作。并查集巧妙地借用了樹結構，使得編程復雜度降低到了令人難以置信的地步；用上 一些遞歸技巧后，各種操作幾乎都能用兩行代碼搞定。而路徑壓縮的好主意，更是整個數(shù)據(jù)結構的畫龍點睛之筆。并查集的效率極高，單次操作的時間復雜度幾乎可 以看作是常數(shù)級別；但由于數(shù)據(jù)結構的實際行為難以預測，精確的時間復雜度分析需要用到不少高深的技巧。

第二名：Knuth-Morris-Pratt字符串匹配算法

關于此算法的介紹，請參考此文：教你從頭到尾徹底理解KMP算法。KMP算法曾經(jīng)落選于二十世紀最偉大的十大算法，但人們顯然不能接受，如此漂亮、高效的KMP算法竟然會落選。所以，此次最終投票產(chǎn)出生，KMP算法排到了第二名。

第三名：BFPRT 算法

1973 年，Blum、Floyd、Pratt、Rivest、Tarjan集體出動，合寫了一篇題為 “Time bounds for selection” 的論文，給出了一種在數(shù)組中選出第 k 大元素的算法，俗稱"中位數(shù)之中位數(shù)算法"。依靠一種精心設計的 pivot 選取方法，該算法從理論上保證了最壞情形下的線性時間復雜度，打敗了平均線性、最壞 O(n^2) 復雜度的傳統(tǒng)算法。一群大牛把遞歸算法的復雜度分析玩弄于骨掌股掌之間，構造出了一個當之無愧的來自圣經(jīng)的算法。

我在這里簡單介紹下在數(shù)組中選出第k大元素的時間復雜度為O（N）的算法：

類似快排中的分割算法：

每次分割后都能返回樞紐點在數(shù)組中的位置s,然后比較s與k的大小

若大的話，則再次遞歸劃分array，

小的話，就遞歸array //s為中間樞紐點元素。

否則返回array，就是partition中返回的值。 //就是要找到這個s。

找到符合要求的s值后，再遍歷輸出比s小的那一邊的元素。

我找到了這個 尋找數(shù)組中第k小的元素的，平均時間復雜度為O（N）的證明：上述程序的期望運行時間，***證明可得O(n)，且假定元素是不同的。

第四名：Quicksort（快速排序）

快速排序算法幾乎涵蓋了所有經(jīng)典算法的所有榜單。它曾獲選二十世紀最偉大的十大算法。

第五名：Floyd-Warshall all-pairs最短路徑算法

關于此算法的介紹，可參考我寫的此文：幾個最短路徑算法比較（http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx）。

d: 二維數(shù)組. d最小花費、或最短路徑的鄰邊。

for k from 1 to n:

for i from 1 to n:

for j from 1 to n:

d = min(d, d + d)

第六名：Gentry's Fully Homomorphic Encryption Scheme（紳士完全同態(tài)加密機制）算法

此算法很漂亮，它允許第三方執(zhí)行任意加密數(shù)據(jù)運算得不到私鑰（不是很了解）。

第七名：Depth First Search、Breadth First Search（深度、廣度優(yōu)先搜索）

它們是許多其他算法的基礎。

第八名：Miller-Rabin作的類似的試驗測試

這個想法是利用素數(shù)的性質(如使用費馬大定理)的小概率尋找見證不數(shù)素數(shù)。如果沒有證據(jù)是足夠的隨機檢驗后發(fā)現(xiàn),這一數(shù)字為素數(shù)。

第九名：Binary Search （二分查找）

在一個有序的集合中查找元素，可以使用二分查找算法，也叫二分搜索。二分查找算法先比較位于集合中間位置的元素與鍵的大小，有三種情況（假設集合是從小到大排列的）：

1.鍵小于中間位置的元素，則匹配元素必在左邊（如果有的話），于是對左邊的區(qū)域應用二分搜索。

2.鍵等于中間位置的元素，所以元素找到。

3.鍵大于中間位置的元素，則匹配元素必在右邊（如果有的話），于是對右邊的區(qū)域應用二分搜索。

另外，當集合為空，則代表找不到。

第十名：Huffman coding（霍夫曼編碼）

霍夫曼編碼(Huffman Coding)是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時所發(fā)明的，并發(fā)表于《一種構建極小多余編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

十一、Cooley-Tukey FFT算法?？焖俑道锶~變換算法。

十二、linear programming，線性規(guī)劃。

十三、Dijkstra 算法。

與上第五一樣，又一種最短路徑算法。

十四、Merge Sort。

歸并排序。

十五、Ford–Fulkerson算法。

網(wǎng)絡***流算法。

十六、輾轉相除法。

在數(shù)學中，輾轉相除法，又稱歐幾里得算法，是求***公約數(shù)的算法，即求兩個正整數(shù)之***公因子的算法。此算法作為TAOCP***個算法被闡述，足見此算 法被重視的程度。它是已知最古老的算法, 其可追溯至3000年前。輾轉相除法***出現(xiàn)于歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的《九章算術》。擴 展的輾轉相除法則構造性地證明了，對任意整數(shù)a和b ，存在一對x、y使得 ax + by = gcd(a, b) 。

十七、RSA加密演算法。

一種加密算法，日后再做詳細介紹。

十八、遺傳算法。

十九、***期望（EM）算法。

此算法入選數(shù)據(jù)挖掘領域十大經(jīng)典算法。在統(tǒng)計計算中，***期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)***似然估計的算法，其 中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。***期望經(jīng)常用在機器學習和計算機視覺的數(shù)據(jù)聚類（Data Clustering）領域。***期望算法經(jīng)過兩個步驟交替進行計算，***步是計算期望（E），利用對隱藏變量的現(xiàn)有估計值，計算其***似然估計值；第二步是***化（M），***化在 E 步上求得的***似然值來計算參數(shù)的值。M 步上找到的參數(shù)估計值被用于下一個 E 步計算中，這個過程不斷交替進行。

二十、數(shù)據(jù)壓縮

數(shù)據(jù)壓縮是通過減少計算機中所存儲數(shù)據(jù)或者通信傳播中數(shù)據(jù)的冗余度，達到增大數(shù)據(jù)密度，最終使數(shù)據(jù)的存儲空間減少的技術。數(shù)據(jù)壓縮在文件存儲和分布式系統(tǒng)領域有著十分廣泛的應用。數(shù)據(jù)壓縮也代表著尺寸媒介容量的增大和網(wǎng)絡帶寬的擴展。

二十一、Hash函數(shù)

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。

二十二、Dynamic Programming（動態(tài)規(guī)劃）。

二十三、堆排序算法。

堆排序算法作為一種快速穩(wěn)定的算法，其平均時間復雜度（最壞也為）O（n*lgn）。當然，在實際應用中，一個實現(xiàn)的好的快速排序算法仍然要優(yōu)于堆排序算法。不過，堆數(shù)據(jù)結構還可以作為高效的優(yōu)先級隊列。

二十四、遞歸與回溯算法。

此倆個算法，相信各位比較熟悉，在此不做贅述。  

二十五、最長公共子序列

最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個數(shù)列 S ，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

動態(tài)規(guī)劃的一個計算最長公共子序列的方法如下：

以兩個序列 X、Y 為例子：

設有二維數(shù)組 f 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有：

      f = same(1,1)

      f = max{f+same(i,j)，f，f}

其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。

此時，f中***的數(shù)便是 X 和 Y 的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。

該算法的空間、時間復雜度均為O(n2)，經(jīng)過優(yōu)化后，空間復雜度可為O(n)，時間復雜度為O(nlogn)。

二十六、紅黑樹的算法與實現(xiàn)

關于紅黑樹，linux內核中有實現(xiàn)。

二十七、A*搜尋算法。

相對于BFS、Dijkstra 等算法，A*搜尋算法作為一種高效的最短路徑搜索算法，如今，已得到日益廣泛的應用。

二十八、圖像特征提取與匹配之SIFT算法

sift，尺度不變特征轉換，是一種電腦視覺的算法用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉不變量，此算法由 David Lowe 在1999年所發(fā)表，2004年完善總結。