作者:july、二零一一年三月七日。

聲明：有一點(diǎn)，希望讀者明白，
以下票選出來的十大算法不等同于，也絕非就是當(dāng)今世界最為經(jīng)典的十大算法。
--------------------------

當(dāng)今世界，已經(jīng)被發(fā)現(xiàn)或創(chuàng)造的經(jīng)典算法數(shù)不勝數(shù)。如果，一定要投票選出你最看重的十大算法，你會(huì)作何選擇列?
最近，有人在stackexchange上發(fā)起了提問，向網(wǎng)友們征集當(dāng)今世界最為經(jīng)典的十大算法。眾人在一大堆入圍算法中進(jìn)行投票，最終得出了呼聲最高的以下十個(gè)算法。

來自圣經(jīng)的十大算法：
發(fā)起人的描述：《來自圣經(jīng)的證明》收集了數(shù)十個(gè)簡(jiǎn)潔而優(yōu)雅的數(shù)學(xué)證明，迅速贏得了大批數(shù)學(xué)愛好者的追捧。如果還有一本《來自圣經(jīng)的算法》，哪些算法會(huì)列入其中呢？現(xiàn)在，朋友們，以下是數(shù)十種候選算法，如果你覺得它是當(dāng)今世界最經(jīng)典的算法，就請(qǐng)您為它投一票.....
最終產(chǎn)生了下面得票數(shù)最高的十大經(jīng)典算法（投票數(shù)統(tǒng)計(jì)截止到2011年3月7日）：

第十名：huffman coding（霍夫曼編碼）
霍夫曼編碼(huffman coding)是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。1952年，david a. huffman在麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（a method for the construction of minimum-redundancy codes）一文。

第九名：binary search （二分查找）
在一個(gè)有序的集合中查找元素，可以使用二分查找算法，也叫二分搜索。二分查找算法先比較位于集合中間位置的元素與鍵的大小，有三種情況（假設(shè)集合是從小到大排列的）：
1.鍵小于中間位置的元素，則匹配元素必在左邊（如果有的話），于是對(duì)左邊的區(qū)域應(yīng)用二分搜索。
2.鍵等于中間位置的元素，所以元素找到。
3.鍵大于中間位置的元素，則匹配元素必在右邊（如果有的話），于是對(duì)右邊的區(qū)域應(yīng)用二分搜索。
另外，當(dāng)集合為空，則代表找不到。

第八名：miller-rabin作的類似的試驗(yàn)測(cè)試
這個(gè)想法是利用素?cái)?shù)的性質(zhì)(如使用費(fèi)馬大定理)的小概率尋找見證不數(shù)素?cái)?shù)。如果沒有證據(jù)是足夠的隨機(jī)檢驗(yàn)后發(fā)現(xiàn),這一數(shù)字為素?cái)?shù)。

第七名：depth first search、breadth first search（深度、廣度優(yōu)先搜索）
它們是許多其他算法的基礎(chǔ)。關(guān)于深度、廣度優(yōu)先搜索算法的具體介紹，請(qǐng)參考此文：教你通透徹底理解：bfs和dfs優(yōu)先搜索算法。

第六名：gentry's fully homomorphic encryption scheme（紳士完全同態(tài)加密機(jī)制）算法。
此算法很漂亮，它允許第三方執(zhí)行任意加密數(shù)據(jù)運(yùn)算得不到私鑰（不是很了解）。

第五名：floyd-warshall all-pairs最短路徑算法
關(guān)于此算法的介紹，可參考我寫的此文：幾個(gè)最短路徑算法比較（http://blog.csdn.net/v_july_v/archive/2011/02/12/6181485.aspx）。
d[]: 二維數(shù)組. d[i,j]最小花費(fèi)、或最短路徑的鄰邊。

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（快速排序）
快速排序算法幾乎涵蓋了所有經(jīng)典算法的所有榜單。它曾獲選二十世紀(jì)最偉大的十大算法（參考這：細(xì)數(shù)二十世紀(jì)最偉大的10大算法）。關(guān)于快速排序算法的具體介紹，請(qǐng)參考我寫的這篇文章：一之續(xù)、快速排序算法的深入分析。

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

我在這里簡(jiǎn)單介紹下在數(shù)組中選出第k大元素的時(shí)間復(fù)雜度為o（n）的算法：
類似快排中的分割算法：

每次分割后都能返回樞紐點(diǎn)在數(shù)組中的位置s,然后比較s與k的大小
若大的話，則再次遞歸劃分array[s..n]，
小的話，就遞歸array[left...s-1] //s為中間樞紐點(diǎn)元素。
否則返回array[s]，就是partition中返回的值。 //就是要找到這個(gè)s。

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

各位可參考在：算法導(dǎo)論上，第九章中，以期望線性時(shí)間做選擇，一節(jié)中，
我找到了這個(gè) 尋找數(shù)組中第k小的元素的，平均時(shí)間復(fù)雜度為o（n）的證明：上述程序的期望運(yùn)行時(shí)間，最后證明可得o(n)，且假定元素是不同的。

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

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

補(bǔ)充：前三名的投票數(shù)，只相差4票，8票。所以這個(gè)排名日后還會(huì)不斷有所變化。但不管最終結(jié)果怎樣，這前十名的算法已經(jīng)基本敲定了。
原投票網(wǎng)址：http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book。

---------------------------------------------------------
怎么樣，上文那些算法，你是否熟悉?如果，現(xiàn)在，我給你一個(gè)投票權(quán)，你會(huì)把票投給哪一個(gè)算法列?ok，咱們也來一次投票吧，請(qǐng)把你的意見，決定權(quán)寫在本文下面的評(píng)論里：

我把已經(jīng)產(chǎn)生的前十名的算法，再寫在下面，方便投票：

第十名：huffman coding（霍夫曼編碼）。
第九名：binary search （二分查找）。
第八名：miller-rabin作的類似的試驗(yàn)測(cè)試。
第七名：depth first search（深度優(yōu)先搜索）。
第六名：紳士完全同態(tài)加密機(jī)制
第五名：floyd-warshall all-pairs最短路徑算法。
第四名：quicksort（快速排序）。
第三名：bfprt 算法。
第二名：knuth-morris-pratt字符串匹配算法。
第一名：union-find。

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

十一、cooley-tukey fft算法?？焖俑道锶~變換算法。關(guān)于傅里葉變換算法的介紹，請(qǐng)參考此文：十、從頭到尾徹底理解傅里葉變換算法、上。

十二、linear programming，線性規(guī)劃。
十三、dijkstra算法。具體介紹，參考此文：二之續(xù)、徹底理解dijkstra算法。

十四、merge sort。歸并排序。
十五、ford–fulkerson算法。網(wǎng)絡(luò)最大流算法。
十六、輾轉(zhuǎn)相除法。
在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法，即求兩個(gè)正整數(shù)之最大公因子的算法。此算法作為taocp第一個(gè)算法被闡述，足見此算法被重視的程度。它是已知最古老的算法, 其可追溯至3000年前。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》（第vii卷，命題i和ii）中，而在中國(guó)則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。擴(kuò)展的輾轉(zhuǎn)相除法則構(gòu)造性地證明了，對(duì)任意整數(shù)a和b ，存在一對(duì)x、y使得 ax + by = gcd(a, b) 。

十七、rsa加密演算法。一種加密算法，日后再做詳細(xì)介紹。
十八、遺傳算法?？蓞⒖急救藢懙年P(guān)于ga 算法的這篇文章：七、遺傳算法 透析ga本質(zhì)。

還猶豫什么列?快投上您寶貴的一票吧。每人限投一票，如果你認(rèn)為那個(gè)算法是最為經(jīng)典的算法，您就在下面的評(píng)論里寫上它的序號(hào)，及算法名稱。
當(dāng)然，如果上文中不曾出現(xiàn)你認(rèn)為最經(jīng)典的算法，你也可以寫在評(píng)論里，為你鐘愛的它投上一票。而后我將考慮您的意見，把您鐘愛的算法也作為一種候選算法，添補(bǔ)上去。:d。

最后，我們自己來做一份十大經(jīng)典算法的排名榜單，也讓世界各地的人看看我們中國(guó)人的意見。怎么樣，還猶豫什么列，趕緊評(píng)論、趕緊投票吧...