當今世界，已經被發(fā)現或創(chuàng)造的算法不計其數。那么，你認為哪些算法是迄今為止較經典的呢？如果，一定要投票選出你最重視的十大算法，你會作何選擇呢?
    最近，有人在StackExchange上發(fā)起了提問，向網友們征集當今世界最為經典的十大算法。眾人在一大堆入圍算法中進行投票，最終得出了呼聲最高的以下十個算法。

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


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


第八名：Miller-Rabin作的類似的試驗測試
    這個想法是利用素數的性質(如使用費馬大定理)的小概率尋找見證不數素數。如果沒有證據是足夠的隨機檢驗后發(fā)現,這一數字為素數。


第七名：Depth First Search、Breadth First Search（深度、廣度優(yōu)先搜索）
    它們是許多其他算法的基礎。關于深度、廣度優(yōu)先搜索算法的具體介紹，請參考此文：教你通透徹底理解：BFS和DFS優(yōu)先搜索算法。


第六名：Gentry's Fully Homomorphic Encryption Scheme（紳士完全同態(tài)加密機制）算法。
    此算法很漂亮，它允許第三方執(zhí)行任意加密數據運算得不到私鑰（不是很了解）。


第五名：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大算法）。關于快速排序算法的具體介紹，請參考我寫的這篇文章：一之續(xù)、快速排序算法的深入分析。


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

    我在這里簡單介紹下在數組中選出第k大元素的時間復雜度為O（N）的算法：
    類似快排中的分割算法：

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

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

  
第二名：Knuth-Morris-Pratt字符串匹配算法
    關于此算法的介紹，請參考此文：六、教你從頭到尾徹底理解KMP算法。KMP算法曾經落選于二十世紀最偉大的十大算法，但人們顯然不能接受，如此漂亮、高效的KMP算法竟然會落選。所以，此次