經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法你了解幾個？想去大廠面試？想成為算法工程師？收下這份全面的復習材料。

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

項目地址：https://github.com/trending

The Algorithms 項目介紹

正如 The Algorithms 項目主頁上介紹的那樣，這是一個使用多種編程語言，實現(xiàn)經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法的開源項目集。這里的「any Programming Language」真是沒有虛假宣傳，我們可以看到 The Algorithms 里從較為流行的 Python、Java、C、C++到 C#、Go、Rust、Kotlin 語言應(yīng)有盡有，當然有的編程語言實現(xiàn)的算法還不是那么的豐富，其中維護較好的還是 Python 和 Java。

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

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

項目地址：https://github.com/TheAlgorithms/Python

部分算法展示

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

排序算法

1. 冒泡排序

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

算法復雜度：

• 最壞 O(n^2)
• 最好 O(n)
• 平均 O(n^2)

交互網(wǎng)頁地址：https://www.toptal.com/developers/sorting-algorithms/bubble-sort

2. 插入排序

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

算法復雜度：

• 最壞 O(n^2)
• 最好 O(n)
• 平均 O(n^2)

 交互網(wǎng)頁地址：https://www.toptal.com/developers/sorting-algorithms/insertion-sort

3. 歸并排序

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

算法復雜度：

• 最壞 O(n log n)
• 最好 O(n)
• 平均 O(n)

交互網(wǎng)頁地址：https://www.toptal.com/developers/sorting-algorithms/merge-sort

4. 快速排序

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

算法復雜度：

• 最壞 O(n^2)
• 最好 O(n log n) 或 O(n) 
• 平均 O(n^2)

交互網(wǎng)頁地址：https://www.toptal.com/developers/sorting-algorithms/quick-sort

5. 希爾排序

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

算法復雜度：

• 最壞 O(nlog2 2n)
• 最好 O(n log n)
• 平均復雜度取決于步長序列

交互網(wǎng)頁地址：https://www.toptal.com/developers/sorting-algorithms/shell-sort

搜索算法

1. 線性搜索算法

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

算法特性：

• 最壞算法復雜度 O(n)
• 最好算法復雜度 O(1)
• 平均算法復雜度 O(n)
• 最壞空間復雜度 O(1) 

2. 二分查找算法

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

• 算法特性：
• 最壞算法復雜度 O(log n)
• 最好算法復雜度 O(1)
• 平均算法復雜度 O(log n)
• 最壞空間復雜度 O(1)

作者簡介

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

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

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