|
【新智元導(dǎo)讀】Github上超過2.7萬星標(biāo)：最全算法及Python實(shí)現(xiàn)。該項(xiàng)目的算法包括排序、搜索等經(jīng)典算法，描述較為詳細(xì)，對(duì)算法原理本身、應(yīng)用場景以及實(shí)現(xiàn)過程的可視化等。 我們討論機(jī)器學(xué)習(xí)的時(shí)候，其實(shí)很多時(shí)候都是在討論算法。今天新智元向大家推薦一個(gè)好資源，用Python實(shí)現(xiàn)所有算法。該項(xiàng)目在Github上已經(jīng)獲得了超過2.7萬星標(biāo)，可以說非常受歡迎了。 該項(xiàng)目主要包括兩方面內(nèi)容：算法的基本原理講解，以及Python代碼實(shí)現(xiàn)，并給出了算法實(shí)現(xiàn)過程的動(dòng)圖，非常直觀易懂。項(xiàng)目地址： https://github.com/TheAlgorithms/Python 排序算法介紹及代碼實(shí)現(xiàn)冒泡算法 冒泡排序，有時(shí)也稱為下沉排序，是一種簡單的排序算法，它反復(fù)遍歷要排序的列表，比較每對(duì)相鄰的項(xiàng)目，如果它們的順序錯(cuò)誤則交換它們。重復(fù)傳遞列表，直到不需要交換，這表明列表已排序。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/bubble-sort 桶排序算法 桶排序（Bucket sort）或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。 雞尾酒排序算法 雞尾酒排序，也叫雙向冒泡排序（Bidirectional Bubble Sort）等。這是冒泡排序的一種變體。不同之處在于，冒泡排序是從低到高比較序列里的每個(gè)元素，而雞尾酒排序從兩個(gè)方向（低到高、高到低）來回排序，效率更高。 代碼實(shí)現(xiàn)： https://en./wiki/Cocktail_shaker_sort 插入排序 插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/insertion-sort 歸并排序 歸并排序（英語：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法，。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/merge-sort 快速排序 快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出，用作按順序放置數(shù)組元素的系統(tǒng)方法。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/quick-sort 堆排序 堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/heap-sort 基數(shù)排序 基數(shù)排序（英語：Radix sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)?；鶖?shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)（Tabulation Machine）上的貢獻(xiàn)。 選擇排序 選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/selection-sort 希爾排序 希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
代碼實(shí)現(xiàn)： https://www./developers/sorting-algorithms/shell-sort 拓?fù)渑判?/strong> 在計(jì)算機(jī)科學(xué)領(lǐng)域，有向圖的拓?fù)渑判蚴瞧漤旤c(diǎn)的線性排序，使得對(duì)于從頂點(diǎn)u到頂點(diǎn)v的每個(gè)有向邊uv，u在排序中都在v之前。例如，圖形的頂點(diǎn)可以表示要執(zhí)行的任務(wù)，并且邊可以表示一個(gè)任務(wù)必須在另一個(gè)任務(wù)之前執(zhí)行的約束; 在這個(gè)應(yīng)用中，拓?fù)渑判蛑皇且粋€(gè)有效的任務(wù)順序。 如果且僅當(dāng)圖形沒有定向循環(huán)，即如果它是有向無環(huán)圖（DAG），則拓?fù)渑判蚴强赡艿?。任何DAG具有至少一個(gè)拓?fù)渑判?，并且已知這些算法用于在線性時(shí)間內(nèi)構(gòu)建任何DAG的拓?fù)渑判颉?/p> 搜索算法線性搜索 線性搜索或順序搜索是一種尋找某一特定值的搜索算法，指按一定的順序檢查數(shù)組中每一個(gè)元素，直到找到所要尋找的特定值為止。是最簡單的一種搜索算法。 二分搜索算法
二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search），對(duì)數(shù)搜索（英語：logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。 插值搜索算法 插值查找(Interpolation Search)是根據(jù)要查找的關(guān)鍵字key與順序表中最大、最小記錄的關(guān)鍵字比較后的查找方法，它假設(shè)輸入數(shù)組是線性增加的（這個(gè)假設(shè)的精確度會(huì)影響算法的效率，但不會(huì)影響算法的正確性）。 跳躍搜索算法 跳躍搜索算法（Jump Search）跟二分查找算法類似，它也是針對(duì)有序序列的查找，只是它是通過查找比較少的元素找到目標(biāo)。當(dāng)然它需要通過固定的跳躍間隔，這樣它相比二分查找效率提高了很多。 快速選擇
快速選擇（英語：Quickselect）是一種從無序列表找到第k小元素的選擇算法。它從原理上來說與快速排序有關(guān)。與快速排序一樣都由托尼·霍爾提出的，因而也被稱為霍爾選擇算法。它在實(shí)際應(yīng)用是一種高效的算法，具有很好的平均時(shí)間復(fù)雜度，然而最壞時(shí)間復(fù)雜度則不理想?？焖龠x擇及其變種是實(shí)際應(yīng)用中最常使用的高效選擇算法。與快速排序一樣，快速選擇一般是以原地算法的方式實(shí)現(xiàn)，除了選出第k小的元素，數(shù)據(jù)也得到了部分地排序。 禁忌搜索 禁忌搜索（Tabu Search，TS，又稱禁忌搜尋法）是一種現(xiàn)代啟發(fā)式算法，由美國科羅拉多大學(xué)教授Fred Glover在1986年左右提出的，是一個(gè)用來跳脫局部最優(yōu)解的搜索方法。其先創(chuàng)立一個(gè)初始化的方案；基于此，算法“移動(dòng)”到一相鄰的方案。經(jīng)過許多連續(xù)的移動(dòng)過程，提高解的質(zhì)量。 加密算法凱撒密碼 凱撒密碼（英語：Caesar cipher），或稱凱撒加密、凱撒變換、變換加密，是一種最簡單且最廣為人知的加密技術(shù)。它是一種替換加密的技術(shù)，明文中的所有字母都在字母表上向后（或向前）按照一個(gè)固定數(shù)目進(jìn)行偏移后被替換成密文。例如，當(dāng)偏移量是3的時(shí)候，所有的字母A將被替換成D，B變成E，以此類推。這個(gè)加密方法是以羅馬共和時(shí)期愷撒的名字命名的，當(dāng)年愷撒曾用此方法與其將軍們進(jìn)行聯(lián)系。 維吉尼亞密碼 維吉尼亞密碼（又譯維熱納爾密碼）是使用一系列凱撒密碼組成密碼字母表的加密算法，屬于多表密碼的一種簡單形式。維吉尼亞密碼曾多次被發(fā)明。該方法最早記錄在吉奧萬·巴蒂斯塔·貝拉索（ Giovan Battista Bellaso）于1553年所著的書《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》（意大利語：La cifra del. Sig. Giovan Battista Bellaso）中。然而，后來在19世紀(jì)時(shí)被誤傳為是法國外交官布萊斯·德·維吉尼亞（Blaise De Vigenère）所創(chuàng)造，因此現(xiàn)在被稱為“維吉尼亞密碼”。 置換密碼 又名取代加密法，是密碼學(xué)中按規(guī)律將文字加密的一種方式。置換密碼中可以用不同字母數(shù)為一單元，例如每一個(gè)或兩個(gè)字母為一單元，然后再作加密。密文接收者解密時(shí)需用原加密方式解碼才可取得原文本。由于拼音文字中字的組成為有限的字母，以英語為例只有26個(gè)字母，組成可能的單元數(shù)較少，因此使用置換密碼相對(duì)較為容易，而且亦可使用簡單機(jī)械進(jìn)行加密；相反，非拼音文字如中文則因單元數(shù)非常大難以使用一般加密方式，必需建立密碼本，然后逐字替換。更何況某些非拼音文字中字字皆由不同大小的字根來組字，較難轉(zhuǎn)換，因此使用置換密碼的示例比較少。 RSA加密算法 RSA加密算法是一種非對(duì)稱加密算法。在公開密鑰加密和電子商業(yè)中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。假如有人找到一種快速因數(shù)分解的算法的話，那么用RSA加密的信息的可靠性就肯定會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到當(dāng)前為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實(shí)際上是不能被解破的。 ROT13算法 ROT13（回轉(zhuǎn)13位，rotate by 13 places，有時(shí)中間加了個(gè)連字符稱作ROT-13）是一種簡易的替換式密碼。它是一種在英文網(wǎng)絡(luò)論壇用作隱藏八卦（spoiler）、妙句、謎題解答以及某些臟話的工具，目的是逃過版主或管理員的匆匆一瞥。ROT13被描述成“雜志字謎上下顛倒解答的Usenet點(diǎn)對(duì)點(diǎn)體”。（Usenet equivalent of a magazine printing the answer to a quiz upside down.）ROT13 也是過去在古羅馬開發(fā)的凱撒加密的一種變體。 異或密碼 異或密碼是密碼學(xué)中一種簡單的加密算法，異或運(yùn)算符常作為更為復(fù)雜的加密算法的組成部分。對(duì)于其本身來說，如果使用不斷重復(fù)的密鑰，利用頻率分析就可以破解這種簡單的異或密碼。如果消息的內(nèi)容被猜出或知道，密鑰就會(huì)泄露。異或密碼值得使用的原因主要是其易于實(shí)現(xiàn)，而且計(jì)算成本小。簡單重復(fù)異或加密有時(shí)用于不需要特別安全的情況下來隱藏信息。 |
|
|
