經典數據結構和算法你了解幾個？想去大廠面試？想成為算法工程師？收下這份全面的復習材料。

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

項目地址：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)

作者簡介

該項目作者是位印度籍工程師，對技術開發非常癡迷，并坦言自己是一個非常有「雄心壯志」的小伙，之后想成為一名企業家。從技術角度看，作者對全棧開發、android 開發、深度學習以及區塊鏈等技術都很感興趣。目前，他已經在 3 家創業公司工作過，并在開發領域積累了 2 年的經驗。

從過往經歷來看，印度小哥的工作經歷還是很「豐富多彩」的，從開始將自己定位為軟件工程師，到目前在 Gojek 任職產品工程師。

 

 Gojek 是印度尼西亞第一家獨角獸公司，于 2010 年在印度尼西亞成立。我們可以將這家公司理解為呼叫中心，將消費者與快遞和兩輪叫車服務連接起來。該公司同時在印度尼西亞、越南、新加坡、泰國和菲律賓都有不少的業務發展。