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

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

項(xiàng)目地址：https://github.com/trending

The Algorithms 項(xiàng)目介紹

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

本文以 The Algorithms 的 Python 項(xiàng)目為例進(jìn)行介紹。

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

項(xiàng)目地址：https://github.com/TheAlgorithms/Python

部分算法展示

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

排序算法

1. 冒泡排序

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

算法復(fù)雜度：

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

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

2. 插入排序

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

算法復(fù)雜度：

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

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

3. 歸并排序

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

算法復(fù)雜度：

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

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

4. 快速排序

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

算法復(fù)雜度：

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

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

5. 希爾排序

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

算法復(fù)雜度：

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

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

搜索算法

1. 線性搜索算法

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

算法特性：

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

2. 二分查找算法

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

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

作者簡(jiǎn)介

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

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

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