有哪些常見的數據結構？基本操作是什么？常見的排序算法是如何實現的？各有什么優缺點？本文簡要分享算法基礎、常見的數據結構以及排序算法。

一 前言

1 為什么要學習算法和數據結構？

• 解決特定問題。
• 深度優化程序性能的基礎。
• 學習一種思想：如何把現實問題轉化為計算機語言表示。

2 業務開發要掌握到程度？

• 了解常見數據結構和算法，溝通沒有障礙。
• 活學活用：遇到問題時知道要用什么數據結構和算法去優化。

二 數據結構基礎

1 什么是數據結構？

數據結構是數據的組織、管理和存儲格式，其使用目的是為了高效的訪問和修改數據。

數據結構是算法的基石。如果把算法比喻成美麗靈動的舞者，那么數據結構就是舞者腳下廣闊而堅實的舞臺。

2 物理結構和邏輯結構的區別？

物理結構就像人的血肉和骨骼，看得見，摸得著，實實在在，如數組、鏈表。

邏輯結構就像人的思想和精神，它們看不見、摸不著，如隊列、棧、樹、圖。

3 線性存儲結構和非線性存儲結構的區別？

• 線性：元素之間的關系是一對一的，如棧、隊列。
• 非線性：每個元素可能連接0或多個元素，如樹、圖。

三 算法基礎

1 什么是算法？

• 數學：算法是用于解決某一類問題的公式和思想。
• 計算機：一系列程序指令，用于解決特定的運算和邏輯問題。

2 如何衡量算法好壞？

• 時間復雜度：運行時間長短。
• 空間復雜度：占用內存大小。

3 怎么計算時間復雜度？

大O表示法（漸進時間復雜度）：把程序的相對執行時間函數T(n)簡化為一個數量級，這個數量級可以是n、n^2、logN等。

推導時間復雜度的幾個原則：

• 如果運行時間是常數量級，則用常數1表示。
• 只保留時間函數中的最高階項。
• 如果最高階項存在，則省去最高項前面的系數。

時間復雜度對比：O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。

不同時間復雜度算法運行次數對比：

4 怎么計算空間復雜度？

常量空間 O(1)：存儲空間大小固定，和輸入規模沒有直接的關系。

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

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

遞歸空間 O(logn)：遞歸是一個比較特殊的場景。雖然遞歸代碼中并沒有顯式的聲明變量或集合，但是計算機在執行程序時，會專門分配一塊內存空間，用來存儲“方法調用棧”。執行遞歸操作所需要的內存空間和遞歸的深度成正比。

5 如何定義算法穩定性？

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

不穩定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現在 b 的后面。

6 有哪些常見算法？

首先要明確：特定算法解決特定問題。

• 字符串：暴力匹配、BM、KMP、Trie等。
• 查找：二分查找、遍歷查找等。
• 排序：冒泡排序、快排、計數排序、堆排序等。
• 搜索：TFIDF、PageRank等。
• 聚類分析：期望最大化、k-meanings、k-數位等。
• 深度學習：深度信念網絡、深度卷積神經網絡、生成式對抗等。
• 異常檢測：k最近鄰、局部異常因子等。
• ......

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

四 常見數據結構

1 數組

1）什么是數組？

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

2）數組的基本操作？

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

2 鏈表

1）什么是鏈表？

鏈表是一種在物理上非連續、非順序的數據結構，由若干個節點組成。

單向鏈表的每一個節點又包含兩部分，一部分是存放數據的變量data，另一部分是指向下一個節點的指針next。

2）鏈表的基本操作？

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

3）鏈表 VS 數組

數組：適合多讀、插入刪除少的場景。

鏈表：適用于插入刪除多、讀少的場景。

3 棧

1）什么是棧？

棧是一種線性邏輯數據結構，棧的元素只能后進先出。最早進入的元素存放的位置叫做棧底，最后進入的元素存放的位置叫棧頂。

一個比喻，棧是一個一端封閉一端的開放的中空管子，隊列是兩端開放的中空管子。

2）如何實現棧？

數組實現：

鏈表實現：

3）棧的基本操作

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

4）棧的應用？

• 回溯歷史，比如方法調用棧。
• 頁面面包屑導航。

4 隊列

1）什么是隊列？

一種線性邏輯數據結構，隊列的元素只能后進后出。隊列的出口端叫做隊頭，隊列的入口端叫做隊尾。

2）如何實現隊列？

數組實現：

鏈表實現：

3）隊列的基本操作？

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

4）隊列的應用

• 消息隊列
• 多線程的等待隊列
• 網絡爬蟲的待爬URL隊列

5 哈希表

1）什么是哈希表？

一種邏輯數據結構，提供了鍵（key）和值（value）的映射關系。