【內附程式碼】工程師技能大全:如何用 Python 寫出所有的演算法?

【為什麼我們要挑選這篇文章】寫程式,懂程式語言只是基礎,「演算法」才是程式的靈魂。有工程師在 Github 分享了各種 Python 演算法的 入門大全 ,讓每個初入行的工程師們可以練習,掌握多個基礎演算法,扎穩馬步,進而挑戰更難的程式技術。(責任編輯:郭家宏)

「《科技報橘》徵才中!跟我們一起定位台灣產業創新力 >> 詳細職缺訊息
快將你的履歷自傳寄至 [email protected]

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

新手如何入門 Python 演算法?

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

Github 傳送門

這個項目主要包括兩部分內容:一是各種演算法的基本原理講解,二是各種演算法的代碼實現。

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

例如在神經網絡部分,給出了 BP 神經網絡、卷積神經網絡、全卷積神經網絡以及感知機等。

卷積神經網絡程式碼示例

程式碼以 Python 文件格式保存在 Github 上,需要的同學可以自行保存下載。

各式演算法原理

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

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

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

交互動畫 傳送門

排序演算法大全

冒泡排序

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

桶排序算法

桶排序(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

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

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

(本文經 大數據文摘 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈Github 标星 2w+,热榜第一,如何用 Python 实现所有算法 〉 。首圖來源:Flickr CC Licensed)

更多實用的程式技巧

寫程式不再崩潰!介紹 5 個 Google 工程師都在用的好習慣
機器學習成效開到最大!介紹 4 個超好用的 Shell 程式技巧
GitHub 神人整理出一份 Python 開源清單:15 個領域、181 個開源項目任你用

點關鍵字看更多相關文章: