10 個必懂演算法圖解：排序、二分、BFS、Dijkstra、DP 全收錄

寫過業務系統幾年後，回頭看演算法這件事的感受很矛盾：日常工作幾乎不會自己刻 Quicksort，呼叫一個 sorted() 就過去了；但每次系統撞到效能天花板、或者要 review 別人寫的索引設計、又或者面試被要求白板寫一段 BFS，演算法就會從「教科書概念」變成「現場救命的工具」。

這篇把工程師日常與面試最常碰到的 10 個經典演算法整理成圖解版，每個演算法附一張示意圖、一段最小可跑的 Python、以及複雜度分析與「實務場景何時用到它」。目標是讓你看完能在三句話內向同事解釋每個演算法在幹嘛，並且看到題目能快速判斷該用哪一招。

一、為什麼經典演算法仍然重要

現代語言內建的標準函式庫已經把絕大多數常用演算法包好了——sorted() 用 Timsort、Python 的 set 與 dict 用 hash table、Java 的 TreeMap 用紅黑樹。表面上看，工程師日常確實不需要自己實作這些東西。但「不需要實作」不等於「不需要理解」。

實務上演算法知識至少在三個場景會出現。第一是當系統撞到效能瓶頸，要從 O(n²) 改成 O(n log n) 才有救——常見於資料庫 join 策略、log 處理、即時推薦排序這類規模放大會痛的場景。第二是面試與系統設計討論，無論是 LeetCode 或是 design interview，能精準地說出「這裡可以用 Union-Find 做 connectivity」會直接影響評估結果。第三是日常 code review，看別人在迴圈裡呼叫 in list（O(n)）而不是 in set（O(1)），這種小問題累積起來就是 P99 失控。

演算法不是要你背實作細節，而是讓你看到問題能 map 到對的工具上。

二、演算法地圖（總覽）

把這 10 個演算法依「問題類型」分群，會比依「實作技巧」更實用：

• 排序類（Quicksort、Mergesort）解決「給我一個有序序列」
• 搜尋類（Binary Search）解決「在有序資料中快速找東西」
• 圖類（BFS、DFS、Dijkstra）解決「節點間的關係/路徑」
• 規劃類（DP、Greedy、Backtracking）解決「最佳化決策序列」
• 連通類（Union-Find）解決「動態維護 group 歸屬」

下面逐一展開。

三、排序家族：Quicksort、Mergesort、Heapsort

排序看起來最簡單，但「為什麼 Python 用 Timsort 而不用純 Quicksort」這個問題本身就值得寫一篇。三種主流的比較式排序在工程選型時各有取捨。

Quicksort 用「選一個 pivot，把比它小的丟左邊，比它大的丟右邊，遞迴處理」的分治思想。平均 O(n log n)、in-place、實作短。缺點是 worst case O(n²)（pivot 一路選到最大或最小值時），所以實務的 Quicksort 一般搭配「三數取中」或隨機選 pivot 來避開最壞情況。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Mergesort 是「先把陣列切兩半各自排好，再合併」。穩定（相等元素相對順序不變）、worst case 也是 O(n log n)。代價是需要 O(n) 額外空間。Mergesort 在外部排序（資料量大過記憶體）特別好用，因為「合併兩個有序檔案」這個 step 可以 streaming 做。

Heapsort 用 binary heap，O(n log n) 保證、in-place、不穩定。實務上 Heapsort 較少獨用，但「Top-K 問題」（找最大/最小的 K 個元素）幾乎都會看到 heap 的影子——維護一個大小為 K 的 min-heap 就能 O(n log K) 解掉。

選型建議：
- 一般用途 → 語言內建的 sort（通常是 Timsort 或 introspective sort，本質是混合策略）
- 穩定排序需求 → Mergesort 系列
- Top-K → heap
- 嵌入式 / 小資料 → insertion sort 仍然有競爭力（n 小時常數低）

四、搜尋：二分搜尋與其變形

二分搜尋的核心思想極簡單：「資料已排序的話，每次砍一半」。但實務上能用對的人比想像中少，常見錯誤是用整數溢位的 mid = (l + r) / 2（在 Java/C++ 大陣列會出事，Python 沒這問題但概念要懂）。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # 避免溢位
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

複雜度 O(log n)。但二分真正的威力不在「找一個確切元素」，而在它的兩個變形：

• lower_bound / upper_bound：找「第一個大於等於 x 的位置」、「第一個大於 x 的位置」。Python 的 bisect.bisect_left / bisect.bisect_right 就是這兩個。實務上做時間序列範圍查詢、區間 count、版本回滾找最近的有效版本，全靠這兩招。
• 答案二分：把「找最小可行解 / 最大不可行解」的問題轉成二分。例：給 N 個任務、M 台機器，問最少要多少時間做完。直接想很難，但二分時間 T、然後檢查「T 時間內能不能做完」就是 O(N log MaxT)。LeetCode hard 題大量題目是這套路。

五、圖演算法：BFS、DFS、Dijkstra

圖（graph）是工程實務最常見的資料結構之一：social network 是圖、API 服務依賴是圖、檔案系統是樹（樹是圖的特例）、Git commit 歷史也是 DAG。

5.1 BFS 廣度優先搜尋

BFS 用 queue 一層一層擴張，特性是「無權圖中找到的第一條路徑必為最短」。實務上 BFS 用在：

• 社群網路「N 度好友」查詢
• 棋盤類最短步數（西洋棋騎士、迷宮、滑板問題）
• 網路爬蟲「先抓淺層連結」策略
• Kubernetes 滾動部署「下一波」運算

from collections import deque

def bfs_shortest(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, 0)])  # (position, steps)
    visited = {start}
    while queue:
        (r, c), steps = queue.popleft()
        if (r, c) == end:
            return steps
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#' and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append(((nr, nc), steps + 1))
    return -1

5.2 DFS 深度優先搜尋

DFS 用 stack（或遞迴，遞迴就是用 call stack）一路鑽到底再回頭。BFS 找最短、DFS 找「能不能到」或「列出所有可能」。

DFS 的實務應用：
- 環路偵測（cycle detection）：判斷有沒有迴圈依賴、判斷 Git rebase 會不會無限循環
- 拓樸排序（topological sort）：build system 決定 module 編譯順序、Airflow DAG 排程
- 連通元件計算：找 social network 中所有獨立 group
- 解迷宮（找出所有解、回溯類問題）

5.3 Dijkstra 最短路徑

當圖的邊有權重（例如距離、延遲、成本），BFS 找的「步數最少」就不等於「成本最低」。Dijkstra 用 priority queue 維護「目前已知最短距離」，每次取出最短的節點 relax 鄰居。

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    dist = {n: float('inf') for n in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

複雜度 O((V + E) log V)。實務上 Dijkstra 出現在：

• 路徑規劃（Google Maps、Uber 派車）
• 網路路由協定（OSPF link-state routing 的核心就是 Dijkstra）
• DAG 的關鍵路徑分析（professional schedule、Airflow critical path）

注意：Dijkstra 不支援負權邊。有負權要用 Bellman-Ford；有負權迴圈要用 SPFA / Johnson。

六、動態規劃：記憶化與表格化

動態規劃（DP）大概是面試與實務「落差最大」的演算法——面試很常考，但日常工程師親自寫 DP 的場合相對少。然而 DP 的思想（把大問題拆成有重疊子問題的小問題，記下答案避免重算）卻無所不在：Redux 的 memoization、React 的 useMemo、SQL 的 query plan caching、編譯器的 common subexpression elimination，全是同一個思想的應用。

DP 有兩種寫法：

• 記憶化遞迴（top-down）：照原問題遞迴，加 cache。直覺、容易寫，但有遞迴深度限制
• 表格化（bottom-up）：從最小子問題開始填表。較快（沒 function call overhead）、可省空間，但需要先想清楚填表順序

經典題：Fibonacci。

# 記憶化遞迴
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# 表格化
def fib_dp(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

DP 的判斷訊號：問題能寫成「最後一步取/不取」的決策樹、子問題有重疊、求最佳值或計數。LeetCode 上 0/1 背包、最長公共子序列（LCS）、最長遞增子序列（LIS）、編輯距離（edit distance）都是經典 DP 題。

實務應用：
- 編輯距離 → spell checker 的 fuzzy match、git diff 的 myers diff 演算法基礎
- LIS → patience sort、stock pattern detection
- 區間 DP → 字串 parsing、文檔分段

七、貪心、Union-Find、回溯三大策略

剩下三個演算法解的是「決策序列」與「動態歸屬」這類問題。

貪心（Greedy）：每一步選當下最佳，期望全局最佳。經典題是「活動選擇」——給 N 個會議，每個有開始與結束時間，問最多排幾個不衝突。直覺會想試所有組合（DP 或 backtracking），但貪心策略「每次選結束時間最早的下一個會議」就 O(n log n) 解掉。

貪心會不會錯？會，而且常常會。判斷貪心是否正確的關鍵是能否證明 exchange argument（任何最佳解都可以「交換」成貪心解而不變差）。Huffman 編碼、Kruskal 最小生成樹、Dijkstra 本身都帶貪心成分。

Union-Find（並查集）：管理「動態 group 歸屬」的資料結構，兩個核心操作 union(a, b)（把 a 跟 b 合併到同一群）、find(a)（a 屬於哪一群）。加上路徑壓縮（path compression）與按秩合併（union by rank）後，攤銷複雜度幾乎是 O(α(n))——α 是 Ackermann 函式的反函式，實務上小於 4。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Union-Find 實務用在 Kruskal 最小生成樹、social network 的 community detection、image processing 的 connected component labeling、線上判題系統的「動態加邊判同群」。

回溯（Backtracking）：系統性地嘗試所有可能解，遇到不行就退一步。本質是 DFS + 剪枝。N-Queens、數獨求解、排列組合題（permutation / combination）、解 sudoku、走迷宮列出所有路徑都是回溯題。剪枝（pruning）的設計直接決定回溯的可行性——數獨完整暴力解是 9^81 種，但加上「同列同行同宮不重複」的剪枝後就秒解。

八、教科書經典補充：七個課堂常見演算法

前面七章涵蓋了工程實務最常碰到的演算法。這一章補充七個演算法課/資料結構課堂上必定會講、面試入門題也常考、但實務日常較少自己刻的「教學經典」。它們的價值在於建立基礎思維——遞迴、排序、回溯、動態規劃——理解它們之後再回頭看工程實務的演算法會更有體感。

8.1 氣泡排序（Bubble Sort）

最直觀的排序：比較相鄰兩個元素，順序錯了就交換，掃過整個陣列就把最大的「冒泡」到最右邊，重複 n-1 輪。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 提早結束：這輪沒換過 = 已排序
            break
    return arr

複雜度 O(n²)、in-place、穩定。實務上絕對不會用——它存在的價值是教學：讓初學者理解「排序」這件事的最基礎流程，以及 Big-O 為什麼重要（10000 筆資料 Quicksort 跟 Bubble Sort 差 600 倍）。

8.2 堆積樹排序（Heap Sort）

利用 binary heap 性質：父節點永遠大於（或小於）子節點。先把陣列建成 max-heap，再不斷把 heap 頂端（最大值）跟結尾交換、然後 sift-down 維持 heap 性質，n 次後就完全排序。

def heap_sort(arr):
    n = len(arr)

    def sift_down(start, end):
        root = start
        while 2 * root + 1 <= end:
            child = 2 * root + 1  # 左子
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1  # 取較大的子
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    # Build max-heap
    for start in range(n // 2 - 1, -1, -1):
        sift_down(start, n - 1)
    # Extract one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end - 1)
    return arr

複雜度 O(n log n)、in-place、不穩定。實務上 Heap Sort 較少獨用，但前面 Top-K 問題提到的「維護大小 K 的 min-heap」就是 heap 結構的衍生應用。

8.3 中間平方法（Mid-Square Method）

歷史上最早期的偽隨機數生成法之一（John von Neumann 1949 提出）：取一個 4 位數種子，平方後取中間 4 位當作下一個隨機數，再平方再取中間，循環下去。

def mid_square(seed, n_digits=4, count=10):
    """從 seed 生成 count 個 n_digits 位偽隨機數"""
    results = []
    x = seed
    for _ in range(count):
        sq = x * x
        s = str(sq).zfill(2 * n_digits)
        mid_start = (len(s) - n_digits) // 2
        x = int(s[mid_start:mid_start + n_digits])
        results.append(x)
    return results

# mid_square(1234, 4, 5) → [5227, 3215, 3362, 3030, 1809, ...]

複雜度 O(1) per call。實務上完全不用——序列很快會退化進迴圈（甚至卡在 0）、隨機性差。但它在教學上是經典：示範了「為什麼設計好的 PRNG 很難」、引出後續 LCG、Mersenne Twister、現代 ChaCha20 等更好的方案。

8.4 青蛙跳台階（Climbing Stairs）

LeetCode 70 題：n 階樓梯，每次可跨 1 階或 2 階，問有幾種跳法。直覺會想列舉，但其實答案是 Fibonacci 數列——到第 n 階的方法數 = 從 n-1 階跳一階上來 + 從 n-2 階跳兩階上來。

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2  # f(1)=1, f(2)=2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# climb_stairs(5) → 8（1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1）

複雜度 O(n) 時間、O(1) 空間（只記前兩個狀態）。延伸題：每次可跨 1/2/3 階就是「pythagorean staircase」、每階有不同 cost 就是「min cost climbing stairs」——核心 DP 思想都一樣：當前狀態 = 前幾個狀態的某種組合。

8.5 巴斯卡三角形（Pascal's Triangle）

從第 0 列只有一個 1 開始，每一列的元素等於上一列「左上 + 右上」相加（邊界視為 0）。生成的三角形每個元素是組合數 C(n, k)。

def pascal_triangle(n):
    """生成前 n 列巴斯卡三角形"""
    triangle = []
    for i in range(n):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
        triangle.append(row)
    return triangle

# pascal_triangle(5) →
# [[1],
#  [1, 1],
#  [1, 2, 1],
#  [1, 3, 3, 1],
#  [1, 4, 6, 4, 1]]

複雜度 O(n²) 時間 + 空間。應用：組合數學（直接讀 C(n, k)）、二項式展開係數、機率計算（伯努利分布的 PDF）、加密理論（Lucas 定理判斷組合數的整除性）。

8.6 河內塔（Tower of Hanoi）

三根柱子 A、B、C，A 上有 n 個由大到小堆好的圓盤，要把它們搬到 C，規則：一次只能搬一個、不能讓大的壓在小的上面。

遞迴的經典啟蒙題：要把 n 個盤從 A 搬到 C，等於「先把上面 n-1 個從 A 搬到 B」→「把最底下的 1 個從 A 搬到 C」→「再把 n-1 個從 B 搬到 C」。三步思路套上去就解了。

def hanoi(n, source, target, helper):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, helper, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, helper, target, source)

# hanoi(3, 'A', 'C', 'B') 輸出 7 步驟

複雜度 O(2^n)——n=20 需要 100 萬步、n=64（傳說中梵天的塔）需要 1844 京步，所以「世界末日」傳說有它的道理。河內塔是理解「遞迴拆解問題」的最佳範例：每一步的決策邏輯很簡單，但整體展開後步數爆炸。

8.7 八皇后（Eight Queens）

8×8 棋盤上放 8 個皇后，要求任意兩個皇后不在同列、同行、同對角線上。問有幾種放法（答案 92 種）。這是回溯（backtracking）演算法的教科書經典題。

def solve_n_queens(n):
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    solutions = []

    def backtrack(row, path):
        if row == n:
            solutions.append(path[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # 剪枝：違反規則就跳過
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            path.append(col)
            backtrack(row + 1, path)
            path.pop()  # 回溯
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)

    backtrack(0, [])
    return solutions

# len(solve_n_queens(8)) → 92

複雜度上界 O(n!)，但「剪枝」（皇后衝突就停止深入）讓實際運行時間遠小於暴力。八皇后展示了回溯演算法的兩個核心：選擇—探索—撤銷 的迴圈，以及 剪枝越早越好 的工程考量。延伸題如數獨求解、排列組合枚舉、子集和問題，都是同一套回溯模板套上不同剪枝規則。

九、Big-O 複雜度速查表

把上面 10 個演算法的時間/空間複雜度整理成表，方便日後查詢：

實務 cheat sheet：

• n ≤ 10：什麼都可以，包括 O(n!)
• n ≤ 100：O(n³) 可以接受
• n ≤ 1000：O(n²) 是上限
• n ≤ 10⁵：要做到 O(n log n)
• n ≤ 10⁷：需要 O(n) 線性掃
• n ≥ 10⁹：只能 O(log n) 或 O(1)

這套估算在 LeetCode 算 1 秒 ≈ 10⁸ 操作，實務系統也大致這個量級。

十、學習資源與下一步

如果這篇看完想繼續深入，幾個高品質學習路徑：

• 教科書：CLRS《Introduction to Algorithms》（俗稱「演算法導論」）仍是經典，理論完整但厚重；Skiena《The Algorithm Design Manual》偏實戰，每章末有「war stories」講作者實際遇過的演算法應用，比較適合工程師
• 互動學習：VisuAlgo（visualgo.net）把 30 多種演算法做成互動動畫，按 step 跑很好理解；algorithm-visualizer（algorithm-visualizer.org）類似但開源、可貢獻
• 練習：LeetCode 前 200 題刷完 90% 工程面試題型都會了，建議按 tag 分類刷而不是隨機刷
• 進階主題：Segment Tree、Fenwick Tree、KMP 字串匹配、A* 啟發式搜尋、二分圖匹配——這些屬於進階但實務也會碰到

最後一個建議是 把演算法當工具不當目的。不要為了刷 LeetCode 而刷，而是讓每一次刷題都對應到「我以後遇到 X 類型問題會想到 Y 招」的肌肉記憶。看到「最短路徑」就反射性想到 BFS / Dijkstra、看到「子問題重疊」就想到 DP、看到「動態 group」就想到 Union-Find——這種反射建立起來後，演算法才真正變成你的能力，而不是考試過後就忘記的知識。

參考資料

• VisuAlgo - 互動式演算法視覺化
• algorithm-visualizer.org - 開源演算法動畫
• CLRS - Introduction to Algorithms (4th Edition)
• The Algorithm Design Manual - Steven Skiena
• LeetCode - Algorithm Problems
• Big-O Cheat Sheet
• Python bisect module
• Wikipedia - Dijkstra's algorithm
• Wikipedia - Union-Find / Disjoint-Set