有哪些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)？基本操作是什么？常見(jiàn)的排序算法是如何實(shí)現(xiàn)的？各有什么優(yōu)缺點(diǎn)？本文簡(jiǎn)要分享算法基礎(chǔ)、常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)以及排序算法。

一 前言

1 為什么要學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)？

• 解決特定問(wèn)題。
• 深度優(yōu)化程序性能的基礎(chǔ)。
• 學(xué)習(xí)一種思想：如何把現(xiàn)實(shí)問(wèn)題轉(zhuǎn)化為計(jì)算機(jī)語(yǔ)言表示。

2 業(yè)務(wù)開(kāi)發(fā)要掌握到程度？

• 了解常見(jiàn)數(shù)據(jù)結(jié)構(gòu)和算法，溝通沒(méi)有障礙。
• 活學(xué)活用：遇到問(wèn)題時(shí)知道要用什么數(shù)據(jù)結(jié)構(gòu)和算法去優(yōu)化。

二 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1 什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織、管理和存儲(chǔ)格式，其使用目的是為了高效的訪問(wèn)和修改數(shù)據(jù)。

數(shù)據(jù)結(jié)構(gòu)是算法的基石。如果把算法比喻成美麗靈動(dòng)的舞者，那么數(shù)據(jù)結(jié)構(gòu)就是舞者腳下廣闊而堅(jiān)實(shí)的舞臺(tái)。

2 物理結(jié)構(gòu)和邏輯結(jié)構(gòu)的區(qū)別？

物理結(jié)構(gòu)就像人的血肉和骨骼，看得見(jiàn)，摸得著，實(shí)實(shí)在在，如數(shù)組、鏈表。

邏輯結(jié)構(gòu)就像人的思想和精神，它們看不見(jiàn)、摸不著，如隊(duì)列、棧、樹、圖。

3 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)的區(qū)別？

• 線性：元素之間的關(guān)系是一對(duì)一的，如棧、隊(duì)列。
• 非線性：每個(gè)元素可能連接0或多個(gè)元素，如樹、圖。

三 算法基礎(chǔ)

1 什么是算法？

• 數(shù)學(xué)：算法是用于解決某一類問(wèn)題的公式和思想。
• 計(jì)算機(jī)：一系列程序指令，用于解決特定的運(yùn)算和邏輯問(wèn)題。

2 如何衡量算法好壞？

• 時(shí)間復(fù)雜度：運(yùn)行時(shí)間長(zhǎng)短。
• 空間復(fù)雜度：占用內(nèi)存大小。

3 怎么計(jì)算時(shí)間復(fù)雜度？

大O表示法（漸進(jìn)時(shí)間復(fù)雜度）：把程序的相對(duì)執(zhí)行時(shí)間函數(shù)T(n)簡(jiǎn)化為一個(gè)數(shù)量級(jí)，這個(gè)數(shù)量級(jí)可以是n、n^2、logN等。

推導(dǎo)時(shí)間復(fù)雜度的幾個(gè)原則：

• 如果運(yùn)行時(shí)間是常數(shù)量級(jí)，則用常數(shù)1表示。
• 只保留時(shí)間函數(shù)中的最高階項(xiàng)。
• 如果最高階項(xiàng)存在，則省去最高項(xiàng)前面的系數(shù)。

時(shí)間復(fù)雜度對(duì)比：O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。

不同時(shí)間復(fù)雜度算法運(yùn)行次數(shù)對(duì)比：

4 怎么計(jì)算空間復(fù)雜度？

常量空間 O(1)：存儲(chǔ)空間大小固定，和輸入規(guī)模沒(méi)有直接的關(guān)系。

線性空間 O(n)：分配的空間是一個(gè)線性的集合，并且集合大小和輸入規(guī)模n成正比。

二維空間 O(n^2)：分配的空間是一個(gè)二維數(shù)組集合，并且集合的長(zhǎng)度和寬度都與輸入規(guī)模n成正比。

遞歸空間 O(logn)：遞歸是一個(gè)比較特殊的場(chǎng)景。雖然遞歸代碼中并沒(méi)有顯式的聲明變量或集合，但是計(jì)算機(jī)在執(zhí)行程序時(shí)，會(huì)專門分配一塊內(nèi)存空間，用來(lái)存儲(chǔ)“方法調(diào)用棧”。執(zhí)行遞歸操作所需要的內(nèi)存空間和遞歸的深度成正比。

5 如何定義算法穩(wěn)定性？

穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后 a 可能會(huì)出現(xiàn)在 b 的后面。

6 有哪些常見(jiàn)算法？

首先要明確：特定算法解決特定問(wèn)題。

• 字符串：暴力匹配、BM、KMP、Trie等。
• 查找：二分查找、遍歷查找等。
• 排序：冒泡排序、快排、計(jì)數(shù)排序、堆排序等。
• 搜索：TFIDF、PageRank等。
• 聚類分析：期望最大化、k-meanings、k-數(shù)位等。
• 深度學(xué)習(xí)：深度信念網(wǎng)絡(luò)、深度卷積神經(jīng)網(wǎng)絡(luò)、生成式對(duì)抗等。
• 異常檢測(cè)：k最近鄰、局部異常因子等。
• ......

其中，字符串、查找、排序算法是最基礎(chǔ)的算法。

四 常見(jiàn)數(shù)據(jù)結(jié)構(gòu)

1 數(shù)組

1）什么是數(shù)組？

數(shù)據(jù)是有限個(gè)相同類型的變量所組成的有序集合。數(shù)組中的每一個(gè)變量被稱為元素。

2）數(shù)組的基本操作？

讀取O(1)、更新O(1)、插入O(n)、刪除O(n)、擴(kuò)容O(n)。

2 鏈表

1）什么是鏈表？

鏈表是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干個(gè)節(jié)點(diǎn)組成。

單向鏈表的每一個(gè)節(jié)點(diǎn)又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針next。

2）鏈表的基本操作？

讀取O(n)、更新O(1)、插入O(1)、刪除O(1)。

3）鏈表 VS 數(shù)組

數(shù)組：適合多讀、插入刪除少的場(chǎng)景。

鏈表：適用于插入刪除多、讀少的場(chǎng)景。

3 棧

1）什么是棧？

棧是一種線性邏輯數(shù)據(jù)結(jié)構(gòu)，棧的元素只能后進(jìn)先出。最早進(jìn)入的元素存放的位置叫做棧底，最后進(jìn)入的元素存放的位置叫棧頂。

一個(gè)比喻，棧是一個(gè)一端封閉一端的開(kāi)放的中空管子，隊(duì)列是兩端開(kāi)放的中空管子。

2）如何實(shí)現(xiàn)棧？

數(shù)組實(shí)現(xiàn)：

鏈表實(shí)現(xiàn)：

3）棧的基本操作

入棧O(1)、出棧O(1)。

4）棧的應(yīng)用？

• 回溯歷史，比如方法調(diào)用棧。
• 頁(yè)面面包屑導(dǎo)航。

4 隊(duì)列

1）什么是隊(duì)列？

一種線性邏輯數(shù)據(jù)結(jié)構(gòu)，隊(duì)列的元素只能后進(jìn)后出。隊(duì)列的出口端叫做隊(duì)頭，隊(duì)列的入口端叫做隊(duì)尾。

2）如何實(shí)現(xiàn)隊(duì)列？

數(shù)組實(shí)現(xiàn)：

鏈表實(shí)現(xiàn)：

3）隊(duì)列的基本操作？

入隊(duì) O(1)、出隊(duì) O(1)。

4）隊(duì)列的應(yīng)用

• 消息隊(duì)列
• 多線程的等待隊(duì)列
• 網(wǎng)絡(luò)爬蟲的待爬URL隊(duì)列

5 哈希表

1）什么是哈希表？

一種邏輯數(shù)據(jù)結(jié)構(gòu)，提供了鍵（key）和值（value）的映射關(guān)系。