Github上超過6.8萬星標：最全算法及Python實現(xiàn)

【導(dǎo)讀】Github上超過6.8萬星標：最全算法及Python實現(xiàn)。該項目的算法包括排序、搜索等經(jīng)典算法，描述較為詳細，對算法原理本身、應(yīng)用場景以及實現(xiàn)過程的可視化等。

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

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

https://github.com/TheAlgorithms/Python

排序算法介紹及代碼實現(xiàn)

冒泡算法

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

代碼實現(xiàn)：

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

桶排序算法

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

雞尾酒排序算法

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

代碼實現(xiàn)：

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

插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

代碼實現(xiàn)：

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

歸并排序

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

代碼實現(xiàn)：

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

快速排序

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

代碼實現(xiàn)：

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

堆排序

堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子節(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

代碼實現(xiàn)：

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

基數(shù)排序

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

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢茫缓?，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

代碼實現(xiàn)：

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

希爾排序

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

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率

但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

代碼實現(xiàn)：

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

拓撲排序

在計算機科學(xué)領(lǐng)域，有向圖的拓撲排序是其頂點的線性排序，使得對于從頂點u到頂點v的每個有向邊uv，u在排序中都在v之前。例如，圖形的頂點可以表示要執(zhí)行的任務(wù)，并且邊可以表示一個任務(wù)必須在另一個任務(wù)之前執(zhí)行的約束; 在這個應(yīng)用中，拓撲排序只是一個有效的任務(wù)順序。如果且僅當圖形沒有定向循環(huán)，即如果它是有向無環(huán)圖（DAG），則拓撲排序是可能的。任何DAG具有至少一個拓撲排序，并且已知這些算法用于在線性時間內(nèi)構(gòu)建任何DAG的拓撲排序。

搜索算法

線性搜索

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

二分搜索算法

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

插值搜索算法

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

跳躍搜索算法

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

快速選擇

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

禁忌搜索

禁忌搜索（Tabu Search，TS，又稱禁忌搜尋法）是一種現(xiàn)代啟發(fā)式算法，由美國科羅拉多大學(xué)教授Fred Glover在1986年左右提出的，是一個用來跳脫局部最優(yōu)解的搜索方法。其先創(chuàng)立一個初始化的方案；基于此，算法“移動”到一相鄰的方案。經(jīng)過許多連續(xù)的移動過程，提高解的質(zhì)量。

加密算法

凱撒密碼

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

維吉尼亞密碼

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

置換密碼

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

RSA加密算法

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

ROT13算法

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

異或密碼

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