Github標星3w+，熱榜第一，如何用Python實現所有演演算法

（點選上方快速關註並設定為星標，一起學Python）

大資料文摘出品

編譯：周素雲、蔣寶尚

學會了Python基礎知識，想進階一下，那就來點演演算法吧！畢竟程式語言只是工具，結構演演算法才是靈魂。

新手如何入門Python演演算法？

幾位印度小哥在GitHub上建了一個各種Python演演算法的新手入門大全。從原理到程式碼，全都給你交代清楚了。為了讓新手更加直觀的理解，有的部分還配了動圖。

標星已經達到3.3W

給出Github地址☟

https://github.com/TheAlgorithms/Python

這個專案主要包括兩部分內容：一是各種演演算法的基本原理講解，二是各種演演算法的程式碼實現。

演演算法的程式碼實現給的資料也比較豐富，除了演演算法基礎原理部分的Python程式碼，還有包括神經網路、機器學習、數學等等程式碼實現。

例如在神經網路部分，給出了BP神經網路、摺積神經網路、全摺積神經網路以及感知機等。

摺積神經網路程式碼示例

程式碼以Python檔案格式儲存在Github上，需要的同學可以自行儲存下載。

再次給出github地址：

https://github.com/TheAlgorithms/Python

在演演算法原理部分主要介紹了排序演演算法、搜尋演演算法、插值演演算法、跳躍搜尋演演算法、快速選擇演演算法、禁忌搜尋演演算法、加密演演算法等。

當然，除了文字解釋之外，還給出了幫助更好理解演演算法的相應資源連結，包括維基百科、動畫互動網站連結。

例如，在一些演演算法部分中，其給出的動畫互動連結，非常完美幫助理解演演算法的執行機制。

互動動畫地址：

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

氣泡排序

氣泡排序，有時也被稱做沉降排序，是一種比較簡單的排序演演算法。這種演演算法的實現是透過遍歷要排序的串列，把相鄰兩個不符合排列規則的資料項交換位置，然後重覆遍歷串列，直到不再出現需要交換的資料項。當沒有資料項需要交換時，則表明該串列已排序。

桶排序演演算法

桶排序(Bucket sort)或所謂的箱排序，是一個排序演演算法，工作的原理是將陣列分到有限數量的桶子裡。每個桶子再個別排序，有可能再使用別的排序演演算法或是以遞迴方式繼續使用桶排序進行排序。

雞尾酒排序

雞尾酒排序，也就是定向氣泡排序，雞尾酒攪拌排序，攪拌排序（也可以視作選擇排序的一種變形），漣漪排序，來回排序或快樂小時排序，都是氣泡排序的一種變形。此演演算法與氣泡排序的不同處在於排序時是以雙向在序列中進行排序。

譯者註：

雞尾酒排序等於是氣泡排序的輕微變形。不同的地方在於從低到高然後從高到低，而氣泡排序則僅從低到高去比較序列裡的每個元素。他可以得到比氣泡排序稍微好一點的效能，原因是氣泡排序只從一個方向進行比對（由低到高），每次迴圈只移動一個專案。

以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問一次序列就可以完成排序，但如果使用氣泡排序則需要四次。但是在隨機數序列的狀態下，雞尾酒排序與氣泡排序的效率都很差勁。

插入排序

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

歸併排序

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

堆（Heap）

堆（Heap）是一種基於比較的排序演演算法。它可以被認為是一種改進的選擇排序。它將其輸入劃分為已排序和未排序的區域，並透過提取最大元素,將其移動到已排序區域來迭代縮小未排序區域。

譯者註：

Heap 始於 J._W._J._Williams 在 1964 年發表的堆排序（heap sort），當時他提出了二叉堆樹作為此演演算法的資料結構。

在佇列中，排程程式反覆提取佇列中第一個作業並執行，因為實際情況中某些時間較短的任務將等待很長時間才能結束，或者某些不短小，但具有重要性的作業，同樣應當具有優先權。堆即為解決此類問題設計的一種資料結構。

基數排序

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

選擇排序

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

Shell排序

ShellSort是插入排序的一種推廣，允許交換相距很遠的項。思路是安排元素串列，以便從任何地方開始，考慮到每個第n個元素都會給出一個排序串列。這樣的串列叫做h排序。等效地，可以被認為是h交錯串列，每個元素都是單獨排序的。

拓撲

拓撲排序或有向圖的拓撲排序是其頂點的線性排序，使得對於從頂點u到頂點v的每個有向邊uv，u在排序中位於v之前。例如，圖的頂點可以表示要執行的任務，並且邊可以表示一個任務必須在另一個之前執行的約束；在這個應用程式中，拓撲排序只是任務的有效序列。當且僅當圖形沒有有向迴圈時，即，如果它是有向非迴圈圖，則拓撲排序是可能的（DAG）。任何DAG都具有至少一個拓撲排序，並且已知演演算法用於線上性時間內構建任何DAG的拓撲排序。

時間複雜折線圖

比較排序演演算法的複雜性（氣泡排序，插入排序，選擇排序）

比較排序演演算法：

Quicksort是一種非常快速的演演算法，但實現起來相當棘手。Bubble sort是一種慢速演演算法，但很容易實現。為了對小資料集進行排序，氣泡排序可能是一個更好的選擇。

線性搜尋

線性搜尋或順序搜尋是用於在串列中查詢標的值的方法。它按順序檢查串列中的每個元素的標的值，直到找到匹配或直到搜尋完所有元素。

假設一個陣列中有N個元素，最好的情況就是要尋找的特定值就是陣列裡的第一個元素，這樣僅需要1次比較就可以。而最壞的情況是要尋找的特定值不在這個陣列或者是陣列裡的最後一個元素，這就需要進行N次比較。

Binary 二進位制搜尋

二進位制搜尋，也稱為半間隔搜尋或對數搜尋，用於查詢已排序陣列中標的值的位置。它將標的值與陣列的中間元素進行比較，如果它們不相等，則標的的一半被消除，並且在剩下的一半上繼續搜尋直到成功。

插值搜尋是一種用於搜尋已按照鍵值的數值排序的陣列中鍵的演演算法。

最先由WW Peterson在1957年描述。插值搜尋類似於人們在電話目錄中搜索名稱的方法（用於訂購書籍條目的關鍵值）：在每個步驟中，演演算法計算剩餘搜尋空間中的位置，基於搜尋空間邊界處的鍵值和所尋找的鍵的值，通常可以透過線性插值來尋找專案。

相比之下，二進位制搜尋總是選擇剩餘搜尋空間的中間，丟棄一半或另一半，這取決於在估計位置找到的金鑰與所尋找的金鑰之間的比較。剩餘的搜尋空間縮小到估計位置之前或之後的部分。線性搜尋僅使用相等性，因為它從一開始就逐個比較元素，忽略任何排序。

平均插值搜尋使得log（log（n））比較（如果元素均勻分佈），其中n是要搜尋的元素的數量。在最壞的情況下（例如，鍵的數值以指數方式增加），它可以構成O（n）比較。

在插值順序搜尋中，插值用於查詢正在搜尋的專案附近的專案，然後使用線性搜尋來查詢確切專案。

跳轉搜尋是指有序串列的搜尋演演算法。它首先檢查所有專案的Lkm，其中K∈N，並且m是塊大小，直到找到大於搜尋關鍵字的專案。為了在串列中找到搜尋關鍵字的確切位置，在子串列L[（k-1）m，km]上執行線性搜尋。

m的最優值是√n，其中n是串列L的長度。因為演演算法的兩個步驟最多都是√n項，所以演演算法在O（√n）時間內執行。這比線性搜尋更好，但比二分搜尋差。優於後者的優點是跳轉搜尋只需要向後跳一次，而二進位制可以向後跳轉到記錄n次。

在最終執行線性搜尋之前，可以透過在子串列上執行多級跳轉搜尋來修改演演算法。對於k級跳躍搜尋，第l級的最佳塊大小ml（從1開始計數）是n（k1）/k。修改後的演演算法將執行k個向後跳轉併在O（kn1/（k+ 1））時間內執行。

快速選擇（Quicksort）是一種從無序串列找到第k小元素的選擇演演算法。它從原理上來說與快速排序有關。與快速排序一樣都由託尼·霍爾提出的，因而也被稱為霍爾選擇演演算法。同樣地，它在實際應用是一種高效的演演算法，具有很好的平均時間複雜度，然而最壞時間複雜度則不理想。快速選擇及其變種是實際應用中最常使用的高效選擇演演算法。

快速選擇的總體思路與快速排序一致，選擇一個元素作為基準來對元素進行分割槽，將小於和大於基準的元素分在基準左邊和右邊的兩個區域。不同的是，快速選擇並不遞迴訪問雙邊，而是隻遞迴進入一邊的元素中繼續尋找。這降低了平均時間複雜度，從O(n log n)至O(n)，不過最壞情況仍然是O(n2)。

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

凱撒密碼

凱撒密碼，也稱為凱撒密碼，移位密碼，凱撒程式碼或凱撒移位，是最簡單和最廣為人知的加密技術之一。

它是一種替換密碼，其中明文中的每個字母都被字母表中的一些固定數量的位置的字母替換。例如，左移3，D將被A替換，E將變為B，依此類推。

該方法以Julius Caesar的名字命名，最初是他在私人通訊中使用了它。由Caesar密碼執行的加密步驟通常作為更複雜的方案的一部分，例如Vigenère密碼，並且仍然在ROT13系統中具有現代應用。與所有單字母替換密碼一樣，Caesar密碼很容易破解，在現代實踐中基本上沒有通訊安全性。

Vigenère密碼

Vigenère密碼是一種透過使用基於關鍵字字母的一系列交織的凱撒密碼來加密字母文字的方法。它是一種多字母替代形式。

Vigenère密碼該方法最初由Giovan Battista Bellaso在其1553年的書“La cifra del”中提出。然而，該計劃後來在19世紀被誤用於BlaisedeVigenère，現在被廣泛稱為“Vigenère密碼”。

雖然該密碼易於理解和實施，但三個世紀以來它一直抵制所有打破密碼的企圖，因此也被稱為這lechiffreindéchiffrable（法語為“難以理解的密碼”）。Friedrich Kasiski是第一個在1863年發表破譯Vigenère密碼的通用方法。

轉置密碼

轉置密碼是一種加密方法，透過該加密方法，明文單元（通常是字元或字元組）所保持的位置根據常規系統移位，使得密文構成明文的排列。也就是說，單位的順序改變（明文被重新排序）。

在數學上，雙字元函式用於加密字元的位置和用於解密的反函式。

RSA (Rivest–Shamir–Adleman)

RSA加密演演算法是一種非對稱加密演演算法。在公開金鑰加密和電子商業中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部檔案中提出了一個與之等效的演演算法，但該演演算法被列入機密，直到1997年才得到公開。

ROT13（“旋轉13個位置”，有時用連字元ROT-13）是一個簡單的字母替換密碼，用字母表後面的第13個字母替換一個字母。ROT13是古羅馬開發的Caesar密碼的特例。

因為基本拉丁字母中有26個字母（2×13），所以ROT13是自身的反轉，也就是說，要撤消ROT13需要相同的演演算法，因此可以使用相同的動作進行編碼和解碼。該演演算法幾乎不提供加密安全性，並且經常被取用為弱加密的典型示例。

Github地址：

https://github.com/TheAlgorithms/Python