參與：Racoon、Jamin

不想做低級碼農，不想成爲前端摳圖達人或是後臺「增刪改查」小王子？那你可能需要好好複習下算法與數據結構。想成爲算法工程師，基礎知識是繞不開的大山。機器之心這次要推薦的項目是數據結構與算法的開源項目集，覆蓋多種主流語言，實現各類經典數據結構及算法。

項目地址：

https://github.com/trending

The Algorithms 項目介紹

正如 The Algorithms 項目主頁上介紹的那樣，這是一個使用多種編程語言，實現經典數據結構與算法的開源項目集。這裏的「any Programming Language」真是沒有虛假宣傳，我們可以看到 The Algorithms 裏從較爲流行的 Python、Java、C、C++到 C#、Go、Rust、Kotlin 語言應有盡有，當然有的編程語言實現的算法還不是那麼的豐富，其中維護較好的還是 Python 和 Java。

本文以 The Algorithms 的 Python 項目爲例進行介紹。

截至目前，該項目已經有 7 萬多星，內容涵蓋加密算法、圖像處理、動態規劃、線性代數、經典機器學習算法、搜索算法、排序算法以及各種數據結構等，單是所實現算法的目錄就有 600 多行……當然，項目作者也指出，該項目的主要目的是用作各種算法的學習資料，項目中的一些實現可能沒有 Python 標準庫中的那麼高效。

項目地址：

https://github.com/TheAlgorithms/Python

部分算法展示

該項目吸引人的地方不單是裏面有豐富的算法實現，部分算法還配有相關解釋、維基百科鏈接和交互網頁鏈接。我們選取了其中的部分算法實現進行展示。

排序算法

1. 冒泡排序

冒泡排序是一種簡單的排序算法。它重複地走訪要排序的數列，一次比較兩個元素，如果它們的順序錯誤就將其交換過來。重複以上過程直到沒有需要交換的元素，即表示完成排序。該算法名字的由來是越小的元素會經由交換慢慢「浮」到數列的頂端。

算法複雜度：

最壞 O(n^2)

最好 O(n)

平均 O(n^2)

交互網頁地址：

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

2. 插入排序

插入排序的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上通常採用 in-place 排序，因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，爲最新元素提供插入空間。

算法複雜度：

最壞 O(n^2)

最好 O(n)

平均 O(n^2)

交互網頁地址：

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

3. 歸併排序

歸併排序是建立在歸併操作上的一種有效的排序算法，由約翰·馮·諾伊曼首次提出。該算法是採用分治法的一個非常典型的應用，且各層分治遞歸可以同時進行。

算法複雜度：

最壞 O(n log n)

最好 O(n)

平均 O(n)

交互網頁地址：

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

4. 快速排序

快速排序算法最早由東尼·霍爾提出。使用分治法策略把一個序列分爲較小和較大 2 個子序列，然後遞歸地排序兩個子序列。

算法複雜度：

最壞 O(n^2)

最好 O(n log n) 或 O(n)

平均 O(n^2)

交互網頁地址：

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

5. 希爾排序

希爾排序也稱遞減增量排序算法，是插入排序的一種更高效的改進版本，按其設計者希爾（Donald Shell）的名字命名，該算法由 1959 年公佈。希爾排序是非穩定排序算法。

算法複雜度：

最壞 O(nlog2 2n)

最好 O(n log n)

平均複雜度取決於步長序列

交互網頁地址：

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

搜索算法

1. 線性搜索算法

線性搜索也稱爲順序搜索，其使用一個循環按順序遍歷整個數組，將每個元素與正在搜索的值進行比較，並在找到該值或遇到數組末尾時停止。

算法特性：

最壞算法複雜度 O(n)

最好算法複雜度 O(1)

平均算法複雜度 O(n)

最壞空間複雜度 O(1)

2. 二分查找算法

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

算法特性：

最壞算法複雜度 O(log n)

最好算法複雜度 O(1)

平均算法複雜度 O(log n)

最壞空間複雜度 O(1)

相關文章