資料結構與算法必備的 50 個代碼實作

資料結構和算法是程式員的内功心法和基本功。無論是人工智能還是其它計算機科學領域，掌握紮實的資料結構和算法知識，往往會助力不少！今天給大家推薦一份不錯的資料結構與算法資源。特點是：全代碼實作！

這份資源的作者王争老師是前 Google 工程師，5 萬+人跟着學的《資料結構和算法之美》專欄作者。他總結了程式員必備的 50 個資料結構與算法，以及相應的代碼實作。開源位址為：

https://github.com/wangzheng0822/algo

我們來看一下這必備的 50 個資料結構與算法究竟包含了哪些内容。

數組 

• 問題：實作一個支援動态擴容的數組
• 問題：實作一個大小固定的有序數組，支援動态增删改操作
• 問題：實作兩個有序數組合并為一個有序數組

連結清單 

• 問題：實作單連結清單、循環連結清單、雙向連結清單，支援增删操作
• 問題：實作單連結清單反轉
• 問題：實作兩個有序的連結清單合并為一個有序連結清單
• 問題：實作求連結清單的中間結點

棧 

• 問題：用數組實作一個順序棧
• 問題：用連結清單實作一個鍊式棧
• 問題：程式設計模拟實作一個浏覽器的前進、後退功能

隊列 

• 問題：用數組實作一個順序隊列
• 問題：用連結清單實作一個鍊式隊列
• 問題：實作一個循環隊列

遞歸 

• 問題：程式設計實作斐波那契數列求值f(n)=f(n-1)+f(n-2)
• 問題：程式設計實作求階乘n!
• 問題：程式設計實作一組資料集合的全排列

排序 

• 問題：實作歸并排序、快速排序、插入排序、冒泡排序、選擇排序
• 問題：程式設計實作O(n)時間複雜度内找到一組資料的第K大元素

二分查找 

• 問題：實作一個有序數組的二分查找算法
• 問題：實作模糊二分查找算法（比如大于等于給定值的第一個元素）

散清單 

• 問題：實作一個基于連結清單法解決沖突問題的散清單
• 問題：實作一個LRU緩存淘汰算法

字元串 

• 問題：實作一個字元集，隻包含a～z這26個英文字母的Trie樹
• 問題：實作樸素的字元串比對算法

二叉樹 

• 問題：實作一個二叉查找樹，并且支援插入、删除、查找操作
• 問題：實作查找二叉查找樹中某個節點的後繼、前驅節點
• 問題：實作二叉樹前、中、後序以及按層周遊

堆 

• 問題：實作一個小頂堆、大頂堆、優先級隊列
• 問題：實作堆排序
• 問題：利用優先級隊列合并K個有序數組
• 問題：求一組動态資料集合的最大Top K

圖 

• 問題：實作有向圖、無向圖、有權圖、無權圖的鄰接矩陣和鄰接表表示方法
• 問題：實作圖的深度優先搜尋、廣度優先搜尋
• 問題：實作Dijkstra算法、A*算法
• 問題：實作拓撲排序的Kahn算法、DFS算法

回溯 

• 問題：利用回溯算法求解八皇後問題
• 問題：利用回溯算法求解0-1背包問題

分治 

• 問題：利用分治算法求一組資料的逆序對個數

動态規劃 

• 問題：0-1背包問題
• 問題：最小路徑和
• 問題：程式設計實作萊文斯坦最短編輯距離
• 問題：程式設計實作查找兩個字元串的最長公共子序列
• 問題：程式設計實作一個資料序列的最長遞增子序列

以上所有的資料結構與算法都配備相應的程式代碼。一大特點是代碼配備多種程式設計語言，例如 Python、C、Java、Go、Scala 等。

​

舉例來說，關于常見的排序算法，例如冒泡排序、插入排序、選擇排序，作者給出了相應的 Python 代碼實作：

"""
Bubble sort, insertion sort and selection sort
冒泡排序、插入排序、選擇排序
Author: Wenru
"""
from typing import List
# 冒泡排序
def bubble_sort(a: List[int]):
length = len(a)
if length <= 1:
return
for i in range(length):
made_swap = False
for j in range(length - i - 1):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
made_swap = True
if not made_swap:
break
# 插入排序
def insertion_sort(a: List[int]):
length = len(a)
if length <= 1:
return
for i in range(1, length):
value = a[i]
j = i - 1
while j >= 0 and a[j] > value:
a[j + 1] = a[j]
j -= 1
a[j + 1] = value
# 選擇排序
def selection_sort(a: List[int]):
length = len(a)
if length <= 1:
return
for i in range(length):
min_index = i
min_val = a[i]
for j in range(i, length):
if a[j] < min_val:
min_val = a[j]
min_index = j
a[i], a[min_index] = a[min_index], a[i]
def test_bubble_sort():
test_array = [1, 1, 1, 1]
bubble_sort(test_array)
assert test_array == [1, 1, 1, 1]
test_array = [4, 1, 2, 3]
bubble_sort(test_array)
assert test_array == [1, 2, 3, 4]
test_array = [4, 3, 2, 1]
bubble_sort(test_array)
assert test_array == [1, 2, 3, 4]
def test_insertion_sort():
test_array = [1, 1, 1, 1]
insertion_sort(test_array)
assert test_array == [1, 1, 1, 1]
test_array = [4, 1, 2, 3]
insertion_sort(test_array)
assert test_array == [1, 2, 3, 4]
test_array = [4, 3, 2, 1]
insertion_sort(test_array)
assert test_array == [1, 2, 3, 4]
def test_selection_sort():
test_array = [1, 1, 1, 1]
selection_sort(test_array)
assert test_array == [1, 1, 1, 1]
test_array = [4, 1, 2, 3]
selection_sort(test_array)
assert test_array == [1, 2, 3, 4]
test_array = [4, 3, 2, 1]
selection_sort(test_array)
assert test_array == [1, 2, 3, 4]
if __name__ == "__main__":
array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
bubble_sort(array)
print(array)
array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
insertion_sort(array)
print(array)
array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
selection_sort(array)
print(array)      

當然，還有其它程式設計語言的代碼實作，這裡就不一一列舉了！

目前，這份資源已經在 GitHub 上收獲了 6000 星了。是一份不錯的資料結構與算法參考代碼。值得一看。最後再附上位址：