當今世界最受人們重視的十大經典算法

當今世界，已經被發現或創造的經典算法數不勝數。如果，一定要投票選出你最看重的十大算法，你會作何選擇列?

    最近，有人在StackExchange上發起了提問，向網友們征集當今世界最為經典的十大算法。衆人在一大堆入圍算法中進行投票，最終得出了呼聲最高的以下十個算法。

    來自聖經的十大算法：

    發起人的描述：《來自聖經的證明》收集了數十個簡潔而優雅的數學證明，迅速赢得了大批數學愛好者的追捧。如果還有一本《來自聖經的算法》，哪些算法會列入 其中呢？現在，朋友們，以下是數十種候選算法，如果你覺得它是當今世界最經典的算法，就請您為它投一票.....

    最終産生了下面得票數最高的十大經典算法（投票數統計截止到2011年3月7日 ）：

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

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

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

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

    1.鍵小于中間位置的元素，則比對元素必在左邊（如果有的話），于是對左邊的區域應用二分搜尋。

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

    3.鍵大于中間位置的元素，則比對元素必在右邊（如果有的話），于是對右邊的區域應用二分搜尋。

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

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

    這個想法是利用素數的性質(如使用費馬大定理)的小機率尋找見證不數素數。如果沒有證據是足夠的随機檢驗後發現,這一數字為素數。

第七名：Depth First Search、Breadth First Search （深度、廣度優先搜尋）

    它們是許多其他算法的基礎。關于深度、廣度優先搜尋算法的具體介紹，請參考此文：教你通透徹底了解：BFS和DFS優先搜尋算法 。

第六名：Gentry's Fully Homomorphic Encryption Scheme （紳士完全同态加密機制）算法。

    此算法很漂亮，它允許第三方執行任意加密資料運算得不到私鑰（不是很了解）。

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

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

d[]: 二維數組. d[i,j]最小花費、或最短路徑的鄰邊。

for k from 1 to n:

  for i from 1 to n:

    for j from 1 to n:

      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

第四名：Quicksort（快速排序）

    快速排序算法幾乎涵蓋了所有經典算法的所有榜單。它曾獲選二十世紀最偉大的十大算法（參考這：細數二十世紀最偉大的10大算法 ）。關于快速排序算法的具體介紹，請參考我寫的這篇文章：一之續、快速排序算法的深入分析 。

第三名：BFPRT 算法

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

    我在這裡簡單介紹下在數組中選出第k大元素的時間複雜度為O（N）的算法：

    類似快排中的分割算法：

每次分割後都能傳回樞紐點在數組中的位置s,然後比較s與k的大小

若大的話，則再次遞歸劃分array[s..n]，

小的話，就遞歸array[left...s-1] //s為中間樞紐點元素。

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

找到符合要求的s值後，再周遊輸出比s小的那一邊的元素。

    各位可參考在：算法導論上，第九章中，以期望線性時間做選擇，一節中，

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

第二名：Knuth-Morris-Pratt字元串比對算法

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

第一名：Union-find

    嚴格地說，并查集是一種資料結構，它專門用來處理集合的合并操作和查詢操作。并查集巧妙地借用了樹結構，使得程式設計複雜度降低到了令人難以置信的地步；用上 一些遞歸技巧後，各種操作幾乎都能用兩行代碼搞定。而路徑壓縮的好主意，更是整個資料結構的畫龍點睛之筆。并查集的效率極高，單次操作的時間複雜度幾乎可 以看作是常數級别；但由于資料結構的實際行為難以預測，精确的時間複雜度分析需要用到不少高深的技巧。并行查找，最終占據了此份榜單的第一名。

    補充：前三名的投票數，隻相差4票，8票。是以這個排名日後還會不斷有所變化。但不管最終結果怎樣，這前十名的算法已經基本敲定了。

    原投票網址 ：http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book 。

---------------------------------------------------------

    怎麼樣，上文那些算法，你是否熟悉?如果，現在，我給你一個投票權，你會把票投給哪一個算法列? ok，咱們也來一次投票吧，請把你的意見，決定權寫在本文下面的評論裡：

我把已經産生的前十名的算法，再寫在下面，友善投票：

一 、Huffman coding（霍夫曼編碼）。

二 、Binary Search （二分查找）。

三 、Miller-Rabin作的類似的試驗測試。

四 、Depth First Search（深度優先搜尋）。

五 、紳士完全同态加密機制

六 、Floyd-Warshall all-pairs最短路徑算法。

七 、Quicksort（快速排序）。

八 、BFPRT 算法。

九 、Knuth-Morris-Pratt字元串比對算法。

十 、Union-find。

為了讓大家有更多的選擇，我再貼出其它幾種同樣經典但暫時未能排進上述榜單前十名的候選算法：

十一、Cooley-Tukey FFT算法。快速傅裡葉變換算法。關于傅裡葉變換算法的介紹，請參考此文：十、從頭到尾徹底了解傅裡葉變換算法、上 。

十二 、linear programming，線性規劃。

十三 、Dijkstra算法。具體介紹，參考此文：二之續、徹底了解Dijkstra算法 。

十四 、Merge Sort。歸并排序。

十五 、Ford–Fulkerson算法。網絡最大流算法。

十六 、輾轉相除法 。

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

十七 、RSA加密演算法。一種加密算法，日後再做詳細介紹。

十八 、遺傳算法。可參考本人寫的關于GA 算法的這篇文章：七、遺傳算法 透析GA本質 。

十九 、最大期望（EM）算法。

    在統計計算中，最大期望（EM）算法是在機率（probabilistic）模型中尋找參數最大似然估計的算法，其中機率模型依賴于無法觀測的隐藏變量 （Latent Variable）。最大期望經常用在機器學習和計算機視覺的資料聚類（Data Clustering）領域。最大期望算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隐藏變量的現有估計值，計算其最大似然估計值；第二 步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用于下一個 E 步計算中，這個過程不斷交替進行。

二十、 資料壓縮

    資料壓縮是通過減少計算機中所存儲資料或者通信傳播中資料的備援度，達到增大資料密度，最終使資料的存儲空間減少的技術。資料壓縮在檔案存儲和分布式系統領域有着十分廣泛的應用。資料壓縮也代表着尺寸媒介容量的增大和網絡帶寬的擴充。

二十一、 Hash函數

    Hash Function是一種從任何一種資料中建立小的數字“指紋”的方法。該函數将資料打亂混合，重新建立一個叫做散列值的指紋。散列值通常用來代表一個短的 随機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散清單和資料進行中，不抑制沖突來差別資料，會使得資料庫記錄更難找到。

二十二、 Dynamic Programming（動态規劃）。關于動态規劃的粗略介紹，請參考此文：三、dynamic programming 。

    還猶豫什麼列?快投上您寶貴的一票吧。每人限投一票，如果你認為那個算法是最為經典的算法，您就在下面的評論裡寫上它的序号，及算法名稱。

    當然，如果上文中不曾出現你認為最經典的算法，你也可以寫在評論裡，為你鐘愛的它投上一票。而後我将考慮您的意見，把您鐘愛的算法也作為一種候選算法，添補上去。:D。

    最後，我們自己來做一份十大經典算法的排名榜單，也讓世界各地的人看看我們中國人的意見。 怎麼樣，還猶豫什麼列，趕緊評論、趕緊投票吧...