【新智元導讀】Github上超過2.7萬星標：最全演算法及Python實現。該項目的演算法包括排序、搜索等經典演算法，描述較為詳細，對演算法原理本身、應用場景以及實現過程的可視化等。

我們討論機器學習的時候，其實很多時候都是在討論演算法。今天新智元向大家推薦一個好資源，用Python實現所有演算法。該項目在Github上已經獲得了超過2.7萬星標，可以說非常受歡迎了。

該項目主要包括兩方面內容：演算法的基本原理講解，以及Python代碼實現，並給出了演算法實現過程的動圖，非常直觀易懂。項目地址：

https://github.com/TheAlgorithms/Python

排序演算法介紹及代碼實現

冒泡演算法

冒泡排序，有時也稱為下沉排序，是一種簡單的排序演算法，它反覆遍歷要排序的列表，比較每對相鄰的項目，如果它們的順序錯誤則交換它們。重複傳遞列表，直到不需要交換，這表明列表已排序。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/bubble-sort

桶排序演算法

桶排序（Bucket sort）或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶里。每個桶再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。

雞尾酒排序演算法

雞尾酒排序，也叫雙向冒泡排序（Bidirectional Bubble Sort）等。這是冒泡排序的一種變體。不同之處在於，冒泡排序是從低到高比較序列里的每個元素，而雞尾酒排序從兩個方向（低到高、高到低）來回排序，效率更高。

代碼實現：

https://en.wikipedia.org/wiki/Cocktail_shaker_sort

插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序，因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/insertion-sort

歸併排序

歸併排序（英語：Merge sort，或mergesort），是創建在歸併操作上的一種有效的排序演算法，。1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/merge-sort

快速排序

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序演算法，最早由東尼·霍爾提出，用作按順序放置數組元素的系統方法。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/quick-sort

堆排序

堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/heap-sort

基數排序

基數排序（英語：Radix sort）是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片製表機（Tabulation Machine）上的貢獻。

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/selection-sort

希爾排序

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
• 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

代碼實現：

https://www.toptal.com/developers/sorting-algorithms/shell-sort

拓撲排序

在計算機科學領域，有向圖的拓撲排序是其頂點的線性排序，使得對於從頂點u到頂點v的每個有向邊uv，u在排序中都在v之前。例如，圖形的頂點可以表示要執行的任務，並且邊可以表示一個任務必須在另一個任務之前執行的約束; 在這個應用中，拓撲排序只是一個有效的任務順序。 如果且僅當圖形沒有定向循環，即如果它是有向無環圖（DAG），則拓撲排序是可能的。任何DAG具有至少一個拓撲排序，並且已知這些演算法用於在線性時間內構建任何DAG的拓撲排序。

搜索演算法

線性搜索

線性搜索或順序搜索是一種尋找某一特定值的搜索演算法，指按一定的順序檢查數組中每一個元素，直到找到所要尋找的特定值為止。是最簡單的一種搜索演算法。

二分搜索演算法

二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search），對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索範圍縮小一半。

插值搜索演算法

插值查找(Interpolation Search)是根據要查找的關鍵字key與順序表中最大、最小記錄的關鍵字比較後的查找方法，它假設輸入數組是線性增加的（這個假設的精確度會影響演算法的效率，但不會影響演算法的正確性）。

跳躍搜索演算法

跳躍搜索演算法（Jump Search）跟二分查找演算法類似，它也是針對有序序列的查找，只是它是通過查找比較少的元素找到目標。當然它需要通過固定的跳躍間隔，這樣它相比二分查找效率提高了很多。

快速選擇

快速選擇（英語：Quickselect）是一種從無序列表找到第k小元素的選擇演算法。它從原理上來說與快速排序有關。與快速排序一樣都由托尼·霍爾提出的，因而也被稱為霍爾選擇演算法。它在實際應用是一種高效的演算法，具有很好的平均時間複雜度，然而最壞時間複雜度則不理想。快速選擇及其變種是實際應用中最常使用的高效選擇演算法。與快速排序一樣，快速選擇一般是以原地演算法的方式實現，除了選出第k小的元素，數據也得到了部分地排序。

禁忌搜索

禁忌搜索（Tabu Search，TS，又稱禁忌搜尋法）是一種現代啟發式演算法，由美國科羅拉多大學教授Fred Glover在1986年左右提出的，是一個用來跳脫局部最優解的搜索方法。其先創立一個初始化的方案；基於此，演算法「移動」到一相鄰的方案。經過許多連續的移動過程，提高解的質量。

加密演算法

凱撒密碼

凱撒密碼（英語：Caesar cipher），或稱凱撒加密、凱撒變換、變換加密，是一種最簡單且最廣為人知的加密技術。它是一種替換加密的技術，明文中的所有字母都在字母表上向後（或向前）按照一個固定數目進行偏移後被替換成密文。例如，當偏移量是3的時候，所有的字母A將被替換成D，B變成E，以此類推。這個加密方法是以羅馬共和時期愷撒的名字命名的，當年愷撒曾用此方法與其將軍們進行聯繫。

維吉尼亞密碼

維吉尼亞密碼（又譯維熱納爾密碼）是使用一系列凱撒密碼組成密碼字母表的加密演算法，屬於多表密碼的一種簡單形式。維吉尼亞密碼曾多次被發明。該方法最早記錄在吉奧萬·巴蒂斯塔·貝拉索（ Giovan Battista Bellaso）於1553年所著的書《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》（義大利語：La cifra del. Sig. Giovan Battista Bellaso）中。然而，後來在19世紀時被誤傳為是法國外交官布萊斯·德·維吉尼亞（Blaise De Vigenère）所創造，因此現在被稱為「維吉尼亞密碼」。

置換密碼

又名取代加密法，是密碼學中按規律將文字加密的一種方式。置換密碼中可以用不同字母數為一單元，例如每一個或兩個字母為一單元，然後再作加密。密文接收者解密時需用原加密方式解碼才可取得原文本。由於拼音文字中字的組成為有限的字母，以英語為例只有26個字母，組成可能的單元數較少，因此使用置換密碼相對較為容易，而且亦可使用簡單機械進行加密；相反，非拼音文字如中文則因單元數非常大難以使用一般加密方式，必需建立密碼本，然後逐字替換。更何況某些非拼音文字中字字皆由不同大小的字根來組字，較難轉換，因此使用置換密碼的示例比較少。

RSA加密演算法

RSA加密演算法是一種非對稱加密演算法。在公開密鑰加密和電子商業中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。假如有人找到一種快速因數分解的演算法的話，那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到當前為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。

ROT13演算法

ROT13（迴轉13位，rotate by 13 places，有時中間加了個連字元稱作ROT-13）是一種簡易的替換式密碼。它是一種在英文網路論壇用作隱藏八卦（spoiler）、妙句、謎題解答以及某些髒話的工具，目的是逃過版主或管理員的匆匆一瞥。ROT13被描述成「雜誌字謎上下顛倒解答的Usenet點對點體」。（Usenet equivalent of a magazine printing the answer to a quiz upside down.）ROT13 也是過去在古羅馬開發的凱撒加密的一種變體。

異或密碼

異或密碼是密碼學中一種簡單的加密演算法，異或運算符常作為更為複雜的加密演算法的組成部分。對於其本身來說，如果使用不斷重複的密鑰，利用頻率分析就可以破解這種簡單的異或密碼。如果消息的內容被猜出或知道，密鑰就會泄露。異或密碼值得使用的原因主要是其易於實現，而且計算成本小。簡單重複異或加密有時用於不需要特別安全的情況下來隱藏信息。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！