搜尋與排序演算法

先看懂：演算法分析的「比較」與「目標」

本章探討兩件事：搜尋（searching） 從一堆資料中找出特定元素，排序（sorting） 把資料重新排列成有序狀態。我們會從 Python in 運算子開始，逐步揭開背後的演算法，並且用「比較次數」當作分析的單位。

顏色語義（整頁通用）

每一節都採用相同的版面：左邊是「視覺化畫布」與「控制列」，右邊是「即時統計」、「對應虛擬碼（pseudo-code）」與「複雜度分析」。請大膽地按 ▶ 開始 看完整動畫，或按 → 單步 一格一格觀察。

循序搜尋：從頭到尾一個一個比

把資料想像成一排櫃子，要找某個物件，最直覺的辦法就是從第 0 格開始、一格一格打開來看。這就是 sequential search，也叫 linear search。它不要求資料有序，是處理一般 list 時最基本的搜尋方法。

有序版本：可以提前停止

如果 list 已經排序好了，就有捷徑：當看到的元素已經比目標大（升冪情況下），後面就不可能有了，可以立刻回傳 False。雖然找到的時候沒省到比較次數，但找不到時平均能少做一半——預期比較次數降到 $n/2$（仍是 $O(n)$，但常數變小）。

二分搜尋：每次砍掉一半的可能位置

當 list 已排序，可以用更聰明的策略：直接看正中間那一個。比目標大就往左半找；比目標小就往右半找；剛好相等就找到了。每次比較排除掉一半，所以總比較次數最多 $\lceil \log_2 n \rceil + 1$。

分而治之的另一種寫法：遞迴版

講義也提供 recursive binary search，本質上和迴圈版本完全等價，但更能體現「divide and conquer」的概念——把問題切成更小的子問題，再對其中一邊遞迴呼叫。

雜湊：用「函數」一次跳到該去的位置

有沒有可能讓搜尋變成 $O(1)$？只要我們事先決定每個值該存哪裡就行。hash function $h(\text{item})$ 把每個值對應到一個槽（slot）的索引。最簡單的 hash 函數是 remainder method：$h(\text{item}) = \text{item} \bmod m$，其中 $m$ 是表的大小。

其他常見的雜湊函數

碰撞解決：除了線性探查還有什麼？

應用：Map ADT (字典/HashTable)

分析：載入因子 $\lambda$ 與比較次數

氣泡排序：相鄰兩個比一比，大的往後送

Bubble sort 的想法很單純：每一輪從頭走到尾，遇到「左邊比右邊大」就交換。經過一輪之後，最大的元素一定會被送到最右邊——就像氣泡浮到水面一樣。下一輪只要處理剩下的部分，依此類推。

選擇排序：每一輪挑出最小者放到前面

Selection sort 跟氣泡排序的比較次數一樣多，但聰明在「每一輪只交換一次」：先掃一遍找出未排序區裡最小的元素，再把它和未排序區的第一格直接交換，就完成一輪。氣泡排序每比一次就可能交換，selection sort 把交換成本壓到最低。（講義版本以「找最小放前面」實作；也有等價的「找最大放後面」變體。）

插入排序：像整理撲克牌

Insertion sort 把陣列分成「已排序」（左半）和「未排序」（右半）兩區。每一輪取出未排序的第一張當 cur_val（current value，當前要插入的值），往左在已排序區裡找出該插入的位置——遇到比它大的，就把它右移一格讓出空間。注意：這裡做的是位移（shift）而不是交換，所以可能比氣泡排序快一點。

希爾排序：插入排序的「跳格」加速版

Shell sort 是 1959 年 Donald Shell 提出的方法。觀察到 insertion sort 對「幾乎排序好」的資料很快，但對亂序資料慢。Shell sort 的策略：先用一個較大的 gap 把陣列拆成數個「子陣列」（每個子陣列的元素彼此相距 gap），對每個子陣列各自做插入排序；接著縮小 gap 再做一次；最後 gap = 1（變成普通的 insertion sort），但此時資料已經幾乎排序好。

講義原始實作（cell 194）

外層 shell_sort 維護當前 sublist_count（折半），對每個 pos_start 呼叫 gap_insertion_sort，把該子陣列做插入排序。

def shell_sort(a_list):
    sublist_count = len(a_list) // 2
    while sublist_count > 0:
        for pos_start in range(sublist_count):
            gap_insertion_sort(a_list, pos_start, sublist_count)
        print("After increments of size", sublist_count, "the list is", a_list)
        sublist_count = sublist_count // 2


def gap_insertion_sort(a_list, start, gap):
    for i in range(start + gap, len(a_list), gap):
        cur_val = a_list[i]
        cur_pos = i
        while cur_pos >= gap and a_list[cur_pos - gap] > cur_val:
            a_list[cur_pos] = a_list[cur_pos - gap]
            cur_pos = cur_pos - gap
        a_list[cur_pos] = cur_val


a_list = [5, 16, 20, 12, 3, 8, 9, 17, 19, 7, 11]
shell_sort(a_list)
print(a_list)

合併排序：分而治之的經典範例

Merge sort 是一個遞迴演算法，分成兩個動作：
(1) Divide 切： 把 list 從中間切成左、右兩半，各自呼叫 merge sort。
(2) Conquer + Merge 合： 兩半都排序好之後，合併成一個有序的大 list——用兩個指標分別走過左、右，每次把較小的那個寫進新 list。
Base case：list 長度 ≤ 1 時自然有序，直接回傳。

快速排序：選一個 pivot，把比它小、比它大的分開

Quicksort 也是分而治之，但策略不同：先選一個元素當 pivot（樞紐值），用一個 partition 過程把陣列重新排成「比 pivot 小 ｜ pivot ｜ 比 pivot 大」三段——pivot 就確定到了它的最終位置。接著對左、右兩段各自遞迴呼叫 quicksort。和 merge sort 不一樣，不需要額外陣列，partition 就地完成。

每個演算法需要什麼底層支援？

同樣的演算法，搬到不同的資料結構上效能可能截然不同——甚至根本跑不動。本節整理本章九個演算法各自能在哪些資料結構上有效執行，重點放在「為什麼某些演算法必須用 Array 而不能用 Linked List」這個關鍵差異上。

兩種基本存取模式

核心對照表：每個演算法所需的資料結構

✓ 自然支援　 △ 可以但效能下降　 ✗ 演算法的核心動作做不到，必須換結構

三個值得記住的關鍵案例

Hash Table 自身的內部結構

選擇底層結構的決策樹

九個演算法一次比較

搜尋演算法

排序演算法

★ 氣泡排序的 $O(n)$ 最佳情況需要使用「短路最佳化」（一輪沒交換就停）。

選擇指南

關鍵概念複習

補充：兩個 PDF 上不容易看出來的細節

這一節針對 PDF 講義中兩個容易卡住的點補完整的逐步追蹤：（A）quadratic probing 把 77、44、55 放到表裡時為什麼會落在那個位置；（B）Map ADT 的 put() 為什麼有 4 個 if/else 分支、每個分支什麼時候會被觸發，以及哪個才是真正的 collision。

A. Quadratic probing 全程追蹤（m = 11）

Step 1 — 前六筆都直接落空槽

此時表的狀態：

idx :  0    1    2    3    4    5    6    7    8    9    10
val : 77    .    .    .   26   93   17    .    .   31    54

Step 2 — 插 44（44 % 11 = 0，撞 77）

Step 3 — 插 55（55 % 11 = 0，撞 77；之後又連撞 4 次）

Step 4 — 插 20（20 % 11 = 9，撞 31）

最終表狀態

idx :  0    1    2    3    4    5    6    7    8    9    10
val : 77   44   20   55   26   93   17    .    .   31    54

B. Map ADT put() 的 4 個分支（最容易跟 collision 搞混的地方）

教科書版本的 put()

把 4 個分支按「碰撞 / 探查」分類

情境設定：4 步剛好走 4 個分支

h = HashTable(size=11)，hash = key % 11，rehash = (p+1) % 11。依序執行下列 4 條 h[key] = val，每一條剛好觸發一個分支：

每一步之後的表狀態（slots / data 同時看）

init     :  slots = [ . , . , . , . , . , . , . , . , . , . , . ]
            data  = [ . , . , . , . , . , . , . , . , . , . , . ]

step 1 (① h[77]="bird"):
            slots = [77 , . , . , . , . , . , . , . , . , . , . ]
            data  = ["bird", . , . , . , . , . , . , . , . , . , . ]

step 2 (② h[77]="eagle"):  ← 同 key 覆寫，slots 不變
            slots = [77 , . , . , . , . , . , . , . , . , . , . ]
            data  = ["eagle", . , . , . , . , . , . , . , . , . , . ]

step 3 (③ h[44]="goat"):   ← collision，rehash 到 slot 1
            slots = [77 , 44 , . , . , . , . , . , . , . , . , . ]
            data  = ["eagle","goat", . , . , . , . , . , . , . , . , . ]

step 4 (④ h[44]="lamb"):   ← 不是 collision，沿著 rehash 路徑找到既存 key 44 並覆寫
            slots = [77 , 44 , . , . , . , . , . , . , . , . , . ]
            data  = ["eagle","lamb", . , . , . , . , . , . , . , . , . ]

注意 slots 在第 4 步完全沒動，只動 data — 這正是「同一個 key 永遠只占一格」的保證。