📌 本頁使用方式（cppds Ch.6–7｜講義 07）
① 照節次讀 ：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。
② 對照講義 ：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 07 與 cppds 原文。
③ 每節做 quiz ：答錯就回到該節重讀，不要往下跳。
④ 最後翻 關鍵詞彙卡（32 張） 自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。
PROLOGUE · 開場
先看懂：演算法分析的「比較」與「目標」 cppds §6.1–6.2
本章探討兩件事：搜尋（searching） 從一堆資料中找出特定元素，排序（sorting） 把資料重新排列成有序狀態。我們會從最樸素的「逐一比對」開始，逐步揭開背後的演算法，並且用「比較次數」當作分析的單位 。
分析的兩個約定
1. 計算單位 = 比較次數。 對搜尋而言，是「拿目標和某個元素比一下」算一次；對排序而言，是「比較兩個元素誰大誰小」算一次。2. 等機率假設。 搜尋成功時，假設目標出現在每個位置的機率都相同；這樣才能合理地討論「平均情況」。
顏色語義（整頁通用）
每一節都採用相同的版面：左邊是「視覺化畫布」與「控制列」，右邊是「即時統計」、「對應虛擬碼（pseudo-code）」與「複雜度分析」。請大膽地按 ▶ 開始 看完整動畫，或按 → 單步 一格一格觀察。
講義完整實作：三種搜尋的 C++ 全文
PART 01 · 循序搜尋
循序搜尋：從頭到尾一個一個比 cppds §6.3
把資料想像成一排櫃子，要找某個物件，最直覺的辦法就是從第 0 格開始、一格一格打開來看 。這就是 sequential search ，也叫 linear search。它不要求資料有序 ，是處理一般 list 時最基本的搜尋方法。
虛擬碼 CODE
bool sequentialSearch (const vector<int >& aList, int item) { size_t pos = 0 ; while (pos < aList.size ()) { if (aList[pos] == item) { return true ; } ++pos; } return false ; }
複雜度
最佳 (item 在頭) $O(1)$
最差 (沒找到) $O(n)$
平均 (找得到) $O(n/2)=O(n)$
為何平均是 n/2？
在「等機率假設」下，目標出現在每個位置的機率相同。若 list 長度是 $n$，找到所需的比較次數為 $1, 2, \ldots, n$，平均為 $\dfrac{1+2+\cdots+n}{n} = \dfrac{n+1}{2}$；用大 O 仍是 $O(n)$。找不到的情形需要 $n$ 次比較 ：必須逐一檢查每一格。
有序版本：可以提前停止
如果 list 已經排序好 了，就有捷徑：當看到的元素已經比目標大（升冪情況下），後面就不可能有了，可以立刻回傳 False。雖然找到的時候沒省到比較次數，但找不到時平均能少做一半 ：預期比較次數降到 $n/2$（仍是 $O(n)$，但常數變小）。
虛擬碼 — orderedSequentialSearch CODE
bool orderedSequentialSearch (const vector<int >& aList, int item) { size_t pos = 0 ;
while (pos < aList.size()) {
if (aList[pos] == item) return true ;
if (aList[pos] > item) return false ;
++pos;
}
return false ;
}
關鍵差異對比表
情境 最佳 最差 平均
item 在 list 中（兩種版本） $1$ $n$ $n/2$ item 不在 （普通版） $n$ $n$ $n$ item 不在 （有序版） $1$ $n$ $n/2$
結論：兩種版本的
大 $O$ 都是 $O(n)$ ，有序版只是
常數變小 。要真正快，得換演算法 → 二分搜尋。
PART 02 · 二分搜尋
二分搜尋：每次砍掉一半的可能位置 cppds §6.4
當 list 已排序 ，可以用更聰明的策略：直接看正中間 那一個。比目標大就往左半找；比目標小就往右半找；剛好相等就找到了。每次比較排除掉一半 ，所以總比較次數最多 $\lceil \log_2 n \rceil + 1$。
當前指標 LIVE
first 0
last 9
midpoint = first + (last-first)/2 4
比較次數 0
結果 —
虛擬碼 CODE
bool binarySearch (const vector<int >& aList, int item) { int first = 0 ; int last = static_cast <int >(aList.size ()) - 1 ; while (first <= last) { int midpoint = first + (last - first) / 2 ; if (aList[midpoint] == item) return true ; if (item < aList[midpoint]) last = midpoint - 1 ; else first = midpoint + 1 ; } return false ; }
複雜度
最佳 (mid 命中) $O(1)$
最差 / 平均 $O(\log n)$
前置條件 必須已排序
為何是 log n？
每次比較讓搜尋範圍變成原本的一半。$n \to n/2 \to n/4 \to \cdots \to 1$，要做 $\log_2 n$ 次切割。數值感受： $n=1{,}000{,}000$ 的 list，循序搜尋最多 $10^6$ 次比較，二分搜尋只要 $\lceil \log_2 10^6 \rceil = 20$ 次！
陷阱
二分搜尋的排序成本 不能忽略。若 list 只搜尋一次，先 $O(n\log n)$ 排序再 $O(\log n)$ 搜尋，反而慢於直接 $O(n)$ 循序搜尋。多次搜尋同一份排序好的資料 時，二分搜尋才划算。
分而治之的另一種寫法：遞迴版
講義也提供 recursive binary search ，本質上和迴圈版本完全等價，但更能體現「divide and conquer 」的概念：把問題切成更小的子問題，再對其中一邊遞迴呼叫。
虛擬碼 — binarySearchRec CODE
bool binarySearchRecRange (const vector<int >& a, int item, int first, int last) { if (first > last) return false ;
int mid = first + (last - first) / 2 ;
if (a[mid] == item) return true ;
if (item < a[mid])
return binarySearchRecRange (a, item, first, mid - 1 );
return binarySearchRecRange (a, item, mid + 1 , last);
}
小細節
若每次遞迴都建構新的子 vector，單一路徑會複製 $n/2+n/4+\cdots=O(n)$ 個元素，因此是 $O(n)$ 時間與 $O(n)$ 峰值元素儲存，而非嚴格的 $O(\log n)$。改傳同一個 const vector<int>& 與 first、last 邊界後，才保留 $O(\log n)$ 比較與 $O(\log n)$ call stack。
PART 03 · 雜湊
雜湊：用「函數」一次跳到該去的位置 cppds §6.5
有沒有可能讓搜尋變成 $O(1)$？只要我們事先決定每個值該存哪裡 就行。hash function $h(\text{item})$ 把每個值對應到一個槽（slot）的索引。最簡單的 hash 函數是 remainder method ：$h(\text{item}) = \text{item} \bmod m$，其中 $m$ 是表的大小。
範例：m = 11，存入 [54, 26, 93, 17, 77, 31]
$54 \bmod 11 = 10$ $26 \bmod 11 = 4$ $93 \bmod 11 = 5$
全部都落在不同槽，
load factor $\lambda = 6/11 \approx 0.55$。
餘數雜湊函數
$h(item) = item \bmod m$
$m = 11$（表大小，建議用質數）
即時統計 LIVE
已用槽數 0 / 11
負載因子 λ 0.00
本次比較次數 0
何謂碰撞 collision
兩個不同的 item 雜湊到同一個 slot 就是碰撞。處理方法：線性探查 往後找第一個空的鏈結法 在該 slot 接一條 list
複雜度
理想 (無碰撞) $O(1)$
線性探查 search $\frac{1}{2}\!\left(1+\frac{1}{1-\lambda}\right)$
鏈結法 search $1 + \lambda/2$
其他常見的雜湊函數
折疊法 folding method
把 item 切成等長的片段 ，加總後再取餘數。例如電話號碼 436-555-4601 切成 43, 65, 55, 46, 01，加總得 $210$；除以 11 得 $h = 210 \bmod 11 = 1$。反轉版本 把每隔一片反過來再相加，例如 34 + 56 + 55 + 64 + 10 = 219 → 219 mod 11 = 10。
平方取中法 mid-square
先把 item 平方，取中間幾位數，再取餘數。
例：item = 44 → $44^2 = 1936$ → 取中間兩位
93 → $93 \bmod 11 = 5$。
範例對照表 54→3, 26→1, 93→9, 17→6, 77→4, 31→8
ⓘ 對 17, 31 這類平方後位數不夠的情況，先補 0 至偶數位再取「正中間兩位」做 mod 11 是統一的做法。例如 $17^2 = 289$ → 補成 0289 → 取 28 → $28 \bmod 11 = 6$；$31^2 = 961$ → 補成 0961 → 取 96 → $96 \bmod 11 = 8$。
字串雜湊 string hashing
字串可以用每個字元的
ordinal value （ASCII 碼）來算：
int hashStr (const string& text, int tableSize) { int sum = 0 ;
for (unsigned char c : text) sum += c;
return sum % tableSize;
}
陷阱： "cat"、"act"、"tac" 全是同樣 ord 總和，會撞在一起（anagrams 衝突）。改良：
用位置當權重 ，例如 $\sum i \cdot \text{ord}(c_i) \bmod m$。
設計目標
理想的 hash 函數應該：易於計算 不能比直接搜尋還慢分布均勻 減少碰撞機率Perfect hash 對特定資料集無碰撞，但不存在通用方法
碰撞解決：除了線性探查還有什麼？
rehash 通式：$\text{rehash}(\text{pos}) = (\text{pos} + \text{skip}) \bmod m$
線性探查 (linear probing) ：skip = 1，每次往後找下一格。簡單但容易產生聚集 (clustering) ：許多碰撞在同一段連續 slot 累積，後續插入會被牽連。+3 探查 (plus-3) ：skip = 3，跳格搜尋。要求 skip 與 $m$ 互質，否則會循環走不完整個表（這也是為何 $m$ 常選質數 ）。平方探查 (quadratic probing) ：skip 不是定值，而是 $1, 4, 9, 16, \ldots$（連續完全平方數）。即 $h, h+1, h+4, h+9, \ldots$。能有效打散聚集。鏈結法 (chaining) ：每個 slot 存一條 list（或其他 collection），所有 hash 到該 slot 的 item 都掛在同一條鏈上。$\lambda$ 可以超過 1。
應用：Map ADT (字典/HashTable)
用 hash 表實作 key-value 字典
Map ADT 是介面概念；
std::unordered_map 是標準函式庫的具體 hash-table 容器。本頁的固定容量
HashTable 只實作
put/get 與顯示輔助，下面同時列出完整 ADT 常見操作作為對照：
操作 語意
HashTable(size) 建立固定容量的教學用 hash table put(key, val) 新增 key–value 對；若 key 已存在則覆寫舊值 get(key) 教學版傳回對應 value；找不到回空字串，因此無法區分「不存在」與「值本來就是空字串」 erase(key) 刪除指定的 key–value 對 size() 回傳目前儲存的 key–value 對總數 in contains(key) 回傳 true/false
class HashTable { public :
void put (int key, string value);
string get (int key);
private :
vector<int > slots; // -1 保留為空槽
vector<string> data;
};
// put 探查一圈仍無空位時 throw overflow_error
關鍵： 用兩個平行 vector (
slots、
data) 分別存 key 和 value，索引位置必須對齊。
get 時要走和
put 一樣的 rehash 路徑，且要偵測「
繞回起點 」(
position == startSlot) 以結束搜尋（代表整個探查鏈都沒有該 key）。
分析：載入因子 $\lambda$ 與比較次數
當 $\lambda$ 變大，效能如何下降？
線性探查 + 開放定址 (open addressing)： 鏈結法 (chaining)：
小實驗
試試用「線性探查」 把 54, 26, 93, 17, 77, 31, 44, 55, 20 全部插入：你會發現 44、55、20 都會發生碰撞，被推到別的槽去。再切換到「鏈結法」 清空、重做一次，會看到撞到的 item 直接掛在槽下面，不會佔走別人的位置。
講義完整範例：從雜湊函數到 Map 的使用畫面
PART 04 · 氣泡排序
氣泡排序：相鄰兩個比一比，大的往後送 cppds §7.2–7.3
Bubble sort 的想法很單純：每一輪從頭走到尾，遇到「左邊比右邊大」就交換。經過一輪之後，最大的元素一定會被送到最右邊 ，就像氣泡浮到水面一樣。下一輪只要處理剩下的部分，依此類推。
虛擬碼 CODE
void bubbleSort (vector<int >& a) { for (int i = a.size () - 1 ; i > 0 ; --i) { for (int j = 0 ; j < i; ++j) { if (a[j] > a[j + 1 ]) swap (a[j], a[j + 1 ]); } } }
複雜度
比較次數 $\binom{n}{2} = \frac{n(n-1)}{2}$
時間 (各情況) $O(n^2)$
空間 $O(1)$
短路最佳化 short bubble
若某一輪都沒發生交換 ，代表已經完全排序了，可以提早結束！這時最佳情況變成 $O(n)$（已排序時只需一輪）。但平均與最差仍是 $O(n^2)$。
虛擬碼 — bubbleSortShort CODE
void bubbleSortShort (vector<int >& aList) { for (int i = static_cast <int >(aList.size()) - 1 ; i > 0 ; --i) {
bool exchanged = false ;
for (int j = 0 ; j < i; ++j) {
if (aList[j] > aList[j + 1 ]) {
swap(aList[j], aList[j + 1 ]);
exchanged = true ;
}
}
if (!exchanged) break ;
}
}
講義完整實作與逐 pass 輸出
PART 05 · 選擇排序
選擇排序：每一輪挑出最大者放到後面 cppds §7.4
Selection sort 跟氣泡排序的比較次數一樣多 ，但聰明在「每一輪只交換一次 」：先掃一遍找出未排序區裡最大 的元素，再把它和未排序區的最後一格 直接交換，就完成一輪。氣泡排序每比一次就可能交換，selection sort 把交換成本壓到最低。（與 cppds 與 HW4 一致：找最大值放到未排序區尾端。）
虛擬碼
void selectionSort (vector<int >& a) { for (int fill = a.size () - 1 ; fill > 0 ; --fill) { int maxPos = 0 ; for (int j = 1 ; j <= fill; ++j) { if (a[j] > a[maxPos]) maxPos = j; } swap (a[maxPos], a[fill]); } }
複雜度
比較次數 $\frac{n(n-1)}{2}$
交換次數 最多 $n-1$
時間 $O(n^2)$
vs. 氣泡
比較次數相同 都是 $O(n^2)$，但 selection sort 每輪最多交換一次 ，氣泡排序每輪可能交換很多次。當「交換成本」很高（例如要移動的物件很大）時，selection sort 表現會比 bubble sort 好。
講義完整實作與逐 pass 輸出
PART 06 · 插入排序
插入排序：像整理撲克牌 cppds §7.5
Insertion sort 把陣列分成「已排序」（左半）和「未排序」（右半）兩區。每一輪取出未排序的第一張當 curVal （current value，當前要插入的值），往左在已排序區裡找出該插入的位置：遇到比它大的，就把它右移一格 讓出空間。注意：這裡做的是位移（shift）而不是交換 ，所以可能比氣泡排序快一點。
虛擬碼
void insertionSort (vector<int >& a) { for (size_t i = 1 ; i < a.size (); ++i) { int curVal = a[i]; size_t curPos = i; while (curPos > 0 && a[curPos - 1 ] > curVal) { a[curPos] = a[curPos - 1 ]; --curPos; } a[curPos] = curVal; } }
複雜度
最佳 (已排序) $O(n)$
最差 / 平均 $O(n^2)$
為什麼適合「幾乎排序好」的資料？
insertion sort 處理已排序資料時非常快：每個 key 只需要一次比較就能確認位置，時間複雜度降到 $O(n)$。如果你正在「插入新資料到已排序的 list 」這個情境，insertion sort 是最自然的選擇。
講義完整實作與逐 pass 輸出
PART 07 · 希爾排序
希爾排序：插入排序的「跳格」加速版 cppds §7.6
Shell sort 是 1959 年 Donald Shell 提出的方法。觀察到 insertion sort 對「幾乎排序好」的資料很快，但對亂序資料慢。Shell sort 的策略：先用一個較大的 gap 把陣列拆成數個「子陣列」（每個子陣列的元素彼此相距 gap），對每個子陣列各自做插入排序；接著縮小 gap 再做一次；最後 gap = 1（變成普通的 insertion sort），但此時資料已經幾乎排序好 。
› 按「開始」執行希爾排序
陣列：
隨機洗牌
套用
gap 序列：
n/2 折半 (Shell 原版)
2^k − 1 = 1,3,7,15,... (Hibbard)
虛擬碼 (對齊講義 §7.6)
void gapInsertionSort (vector<int >&, int , int );void shellSort (vector<int >& a) { int gap = a.size () / 2 ; while (gap > 0 ) { for (int start = 0 ; start < gap; ++start) gapInsertionSort (a, start, gap); gap /= 2 ; } } void gapInsertionSort (vector<int >& a, int start, int gap) { for (int i = start + gap; i < a.size (); i += gap) { int curVal = a[i]; int curPos = i; while (curPos >= gap && a[curPos-gap] > curVal) { a[curPos] = a[curPos-gap]; curPos -= gap; } a[curPos] = curVal; } }
複雜度
時間 (依 gap 序列) $O(n^{3/2}) \sim O(n^2)$
Hibbard 序列 $2^k-1$ $O(n^{3/2})$
空間 $O(1)$
關鍵直覺
當 gap 大時：每個子陣列很短，大跨度的調整很快 ，亂度迅速降低。小範圍的微調很便宜 。程式碼短、不需要遞迴、空間 $O(1)$ ，是嵌入式系統與小型應用常見的選擇。
講義完整實作與逐 pass 輸出
PART 08 · 合併排序
合併排序：分而治之的經典範例 cppds §7.7
Merge sort 是一個遞迴演算法，分成兩個動作：(1) Divide 切： 把 list 從中間切成左、右兩半，各自呼叫 merge sort。(2) Conquer + Merge 合： 兩半都排序好之後，合併 成一個有序的大 list：用兩個指標分別走過左、右，每次把較小的那個寫進新 list。
虛擬碼
void mergeSort (vector<int >& a) { if (a.size () <= 1 ) return ; size_t mid = a.size () / 2 ; vector<int > left(a.begin (), a.begin () + mid); mergeSort (left); vector<int > right(a.begin () + mid, a.end ()); mergeSort (right); // merge left and right back into a size_t i = 0 , j = 0 , k = 0 ; while (i < left.size () && j < right.size ()) { if (left[i] <= right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; } // then copy either remaining tail while (i < left.size ()) a[k++] = left[i++]; while (j < right.size ()) a[k++] = right[j++]; }
複雜度
時間 (各情況) $O(n \log n)$
空間 $O(n)$ 額外
是否穩定 穩定 ✓
為何是 n log n？
每一層遞迴把問題切成兩半 → 共 $\log_2 n$ 層；每一層的「merge 動作」總共要看過所有 $n$ 個元素 → 每層 $O(n)$。整體 $O(n) \times O(\log n) = O(n \log n)$。比較式排序的下界 ：任何只透過比較來排序的演算法都至少要 $\Omega(n\log n)$，merge sort 達到這個下界。
代價：額外空間
merge sort 需要額外 $O(n)$ 的暫存空間 來存 L、R 半段（實作中需額外配置 L、R 兩段暫存 vector）。處理超大資料時，這個記憶體開銷可能成為問題。
講義完整實作與逐 pass 輸出
PART 09 · 快速排序
快速排序：選一個 pivot，把比它小、比它大的分開 cppds §7.8
Quicksort 也是分而治之，但策略不同：先選一個元素當 pivot （樞紐值），用一個 partition 過程把陣列重新排成「比 pivot 小 ｜ pivot ｜ 比 pivot 大 」三段，pivot 就確定到了它的最終位置 。接著對左、右兩段各自遞迴呼叫 quicksort。和 merge sort 不一樣，不需要額外陣列 ，partition 就地完成。
partition 的雙指標技術
從 pivot 右邊開始：leftMark 從左往右走、找大於 pivot 的 ；rightMark 從右往左走、找小於 pivot 的 。兩者都停下時就交換它們。當 leftMark 越過 rightMark 之後，把 pivot 和 rightMark 交換，pivot 就到位了。
› 按「開始」執行快速排序
陣列：
隨機洗牌
套用
pivot 策略：
第一個 (講義版本)
三者取中 median-of-three
即時狀態 LIVE
當前 pivot —
左右範圍 [first, last] —
leftMark —
rightMark —
虛擬碼
void quickSortHelper (vector<int >& a, int first, int last) { if (first < last) { int split = partition (a, first, last); quickSortHelper (a, first, split - 1 ); quickSortHelper (a, split + 1 , last); } }
複雜度
最佳 / 平均 $O(n \log n)$
最差 (pivot 極差) $O(n^2)$
空間 (遞迴) $O(\log n)$ 期望
最差情況：當 pivot 是極端值
若每次選的 pivot 剛好是最大或最小（例如已排序的陣列 + 「選第一個當 pivot」策略），每次只能切下 1 個元素 → 退化成 $O(n^2)$。median-of-three 取「first、middle、last 三者中位數」當 pivot，能大幅降低最差情況的機率，對「幾乎排序好」的資料尤其有效。
vs. merge sort
quicksort 就地排序，不需要 $O(n)$ 額外空間 ，常數係數也比 merge sort 小，實務上通常更快 。但 quicksort 不穩定、且最差是 $O(n^2)$；merge sort 任何情況都是 $O(n\log n)$ 且穩定。C++ 標準只規定 std::sort() 的最差比較次數為 $O(n\log n)$，不指定實作策略；常見標準函式庫採 introsort 類混合實作。std::stable_sort() 保證穩定，但實作方式同樣由函式庫決定。
講義練習：讓 quicksort 支援降冪排序（Exercise 3）
講義的課後練習：替 quickSort 加一個 bool descending 參數，讓同一套程式碼既能升冪也能降冪。
解法漂亮在「幾乎什麼都不用改」：遞迴骨架原封不動，只有 partition 裡兩個內層 while 的比較方向要翻面 。
升冪時 leftMark 找「大於 pivot 的」往右送；降冪時反過來找「小於 pivot 的」。
入口與遞迴：只是把參數往下傳 CODE
void quickSort (vector<int >& aList, bool descending = false ) { quickSortHelper (aList, 0 , aList.size() - 1 , descending);
}
void quickSortHelper (vector<int >& aList, int first, int last, bool descending) {
if (first < last) {
int split = partition (aList, first, last, descending);
quickSortHelper (aList, first, split - 1 , descending);
quickSortHelper (aList, split + 1 , last, descending);
}
}
partition：只翻兩個比較方向 CODE
while (!done) { if (descending) { // 降冪：方向翻面
while (leftMark <= rightMark && aList[leftMark] >= pivotVal) leftMark++;
while (leftMark <= rightMark && aList[rightMark] <= pivotVal) rightMark--;
} else { // 升冪：講義原版
while (leftMark <= rightMark && aList[leftMark] <= pivotVal) leftMark++;
while (leftMark <= rightMark && aList[rightMark] >= pivotVal) rightMark--;
}
if (rightMark < leftMark) done = true ;
else swap (aList[leftMark], aList[rightMark]);
}
swap (aList[first], aList[rightMark]); // pivot 到位
同一份 {54, 26, 93, 17, 77, 31, 44, 55, 20}：升冪得 17 20 26 31 44 54 55 77 93、降冪得 93 77 55 54 44 31 26 20 17。分割的想法一套通吃，變的只有「誰算放錯邊」。
講義完整實作與逐 partition 輸出
PART 10 · 依賴的資料結構
每個演算法需要什麼底層支援？ 課程補充
同樣的演算法，搬到不同的資料結構上效能可能截然不同，甚至根本跑不動。本節整理本章九個演算法各自能在哪些資料結構上有效執行 ，重點放在「為什麼某些演算法必須 用 Array 而不能用 Linked List」這個關鍵差異上。
兩種基本存取模式
Random Access — 隨機存取 FAST
可以用「索引」$O(1)$ 跳到任意位置 。陣列 (Array) 最典型：記憶體連續，a[i] 直接用 base + i × sizeof(T) 算出位址即可。代表結構 C++ vector、C 風格 array、Java ArrayList關鍵動作 a[i] = $O(1)$，a[i] = v = $O(1)$，連續走訪 cache 友善
Sequential Access — 循序存取 SLOW INDEX
只能從頭往後一個一個走 （透過 node.next）；想跳到第 $k$ 個必須走過前 $k-1$ 個 → $O(k)$。代表結構 Linked List (鏈結串列)、Iterator、Generator、Stream優勢 中間插入/刪除 $O(1)$（已知前一節點時）、不用連續記憶體
核心對照表：每個演算法所需的資料結構
演算法
必要屬性
Array
Linked List
關鍵原因
循序搜尋
可逐一拜訪
✓ 自然
✓ 自然
只需 sequential access，兩種結構都可以
有序循序搜尋
可逐一拜訪 + 有序
✓
✓
遇到 a[pos] > item 即停，鏈結串列也行
二分搜尋 $O(1)$ 隨機存取 + 有序
✓ 必須
✗ 不行
跳到 midpoint 在鏈結串列要 $O(n)$，破壞 $\log n$
雜湊表 (Hashing)
固定大小 array 當底層
✓ 必須
✗
$h(\text{item}) \to$ slot 索引，必須隨機存取
氣泡排序
隨機存取 + 可變
✓
△ 慢但可
需要 a[j] 與 a[j+1] 的相鄰比較交換
選擇排序
隨機存取 + 可交換
✓
△ 慢但可
找到 maxPos 後 swap a[maxPos] ↔ a[fill]
插入排序
隨機存取（位移）
✓
△ 變體可行
位移 a[curPos-1] → a[curPos] 在 array 是 $O(1)$
希爾排序 隨機存取（gap 跳格）
✓ 必須
✗ 不行
需要 a[pos − gap]，鏈結串列做不到「跳 gap 格」
合併排序 可拆分 + 可合併
✓ 但需 $O(n)$ 額外空間
✓ 更佳！ $O(1)$ 額外空間
鏈結串列 merge 只重接指標，不必複製 ★
快速排序 雙向隨機存取（雙指標）
✓ 必須
✗ 不行
partition 需要左右雙指標雙向走，singly-linked 無法
✓ 自然支援
△ 可以但效能下降
✗ 演算法的核心動作做不到，必須換結構
三個值得記住的關鍵案例
為何「Binary Search 必須要 Array」？
Binary search 每次跳到 midpoint = first + (last-first)/2。從頭走 midpoint 步 ，每次比較都要 $O(n)$排序好的資料若以 Linked List 儲存，binary search 沒有意義 ，必須轉成 Array（或一開始就用 Array）。
為何「Quick Sort 不能用 Singly Linked List」？
Partition 需要兩個指標 leftMark、rightMark：一個從左往右、一個從右往左 走。單向鏈結串列只能從左往右 （每個 node 只有 next，沒有 prev），rightMark-- 沒有有效率的實作方式。雖然 doubly-linked list 可以雙向走，但每次比較都要追指標、cache miss 嚴重，常數係數比 Array 大太多。快速排序的教科書版本永遠用 Array 來講 ：partition 的優美只在 Array 上才成立。
為何「Merge Sort 反而更 適合 Linked List」？★ 反直覺！
Array 版的 merge sort 需要 $O(n)$ 額外空間存 L、R 子陣列。但Linked List 版的 merge 只需重接指標 ：把較小的 node 從左/右串列上「摘下」，接到結果串列尾端，完全不需要複製資料 ，額外空間只有 $O(1)$（幾個指標變數而已）。更省記憶體、更乾淨 。所以當資料天生就是 linked list 形式（functional 語言、stream pipeline、某些 OS 內部資料結構），merge sort 是首選排序法。實務小知識： Java 的 java.util.LinkedList.sort() 內部就是先轉成 Array 再用 mergesort，因為 cache 表現更好；但概念上 linked list mergesort 是經典範例。
Hash Table 自身的內部結構
Hash Table 是什麼底層結構？答：仍然是 Array！
Hash table
本身的底層 就是一個固定大小（$m$）的 Array：
線性 / 平方探查 純 Array of (key, value)；衝突時往別的 slot 找空位
鏈結法 chaining Array of Linked List ；每個 slot 是一條 list 的 head
Map ADT 實作（講義版本） 兩個平行 Array：slots[] 存 key、data[] 存 value，索引位置一一對齊
這就是為何 C++
unordered_map、Java
HashMap 內部都看得到 Array：雜湊表離不開 random access。
選擇底層結構的決策樹
給定情境，該選哪種底層結構？
① 需要快速隨機存取 + 排序後重複搜尋？ Array + 排序 $O(n\log n)$ 一次 + 二分搜尋 $O(\log n)$ 多次② 大量「鍵值對」key-value 查詢？ Hash Table （底層 Array），平均 $O(1)$ 查詢③ 頻繁從中間插入/刪除元素？ Linked List ，必要時排序選 merge sort（$O(1)$ 額外空間版本）④ 資料天然有序、僅追加（如 log）？
本章其他資料結構的關係（前情提要）
本書前幾章學過的資料結構，在本章扮演的角色：
Stack： quick sort / merge sort 的遞迴呼叫堆疊 就是 stack；如果改寫成 iterative 版本，會明確使用一個 stack 來模擬遞迴。Queue： iterative merge sort 的「bottom-up」版本可以用 queue 來組織待合併的子串列。Linked List： chaining 法雜湊表的 collision bucket、merge sort 的最佳載體。Tree： 合併排序的遞迴呼叫關係本身就是一棵二元樹 （PART 08 的視覺化就是把這棵樹畫出來）。
搜尋與排序不是孤立的章節：它們是建立在前面所有資料結構之上的
應用範例 。
REFERENCE · 比較總覽
九個演算法一次比較 總覽
搜尋演算法
演算法 最佳 平均 最差 前置條件 空間
循序搜尋 $O(1)$ $O(n)$ $O(n)$ 無 $O(1)$ 循序搜尋 (有序) $O(1)$ $O(n/2)$ $O(n)$ 已排序 $O(1)$ 二分搜尋 $O(1)$ $O(\log n)$ $O(\log n)$ 已排序 $O(1)$ 雜湊 (理想) $O(1)$ $O(1)$ $O(n)$ 有 hash 函數 $O(m)$
排序演算法
演算法 最佳 平均 最差 空間 穩定 就地
氣泡排序 Bubble $O(n)$ ★ $O(n^2)$ $O(n^2)$ $O(1)$ ✓ ✓ 選擇排序 Selection $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ ✗ ✓ 插入排序 Insertion $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ ✓ ✓ 希爾排序 Shell $O(n\log n)$ $O(n^{3/2})$ $O(n^2)$ $O(1)$ ✗ ✓ 合併排序 Merge $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n)$ ✓ ✗ 快速排序 Quick $O(n\log n)$ $O(n\log n)$ $O(n^2)$ $O(\log n)$ ✗ ✓
★ 氣泡排序的 $O(n)$ 最佳情況需要使用「短路最佳化」 （一輪沒交換就停）。
選擇指南
情境 建議演算法 原因
資料量小 (n < 20) 插入排序 常數小、邏輯簡單 資料幾乎已排序 插入排序 / 氣泡 (短路) $O(n)$ 最佳 需要穩定且效能保證 合併排序 始終 $O(n\log n)$、穩定 記憶體有限 希爾 / 快速排序 就地排序 實務通用、最快 快速排序 (含中位數策略) 常數最小 大量搜尋同份資料 排序後二分搜尋 / 雜湊表 建立成本攤提 需要 $O(1)$ 平均搜尋 雜湊表 用空間換時間
關鍵概念複習
穩定 stable
當兩個元素「比較相等」時，若排序後它們的相對順序不變 ，演算法就是穩定的。在多鍵排序（先按姓名再按部門）時很重要。
就地 in-place
僅使用 $O(1)$ 或 $O(\log n)$ 額外空間（除了輸入本身）的排序。merge sort 不是就地（需要 $O(n)$ 暫存），quick sort 是（只需遞迴堆疊）。
比較式排序的下界
任何只透過「兩兩比較」來排序的演算法，最差情況都至少要 $\Omega(n\log n)$ 次比較。merge / heap / 平均下的 quick sort 都達到這個下界。要打破它必須使用「非比較」方法，例如 counting sort 或 radix sort（要求資料形態特定）。
SUP · 補充
補充：兩個 PDF 上不容易看出來的細節 課程補充
這一節針對 PDF 講義中兩個容易卡住的點補完整的逐步追蹤：（A）quadratic probing 把 77、44、55 放到表裡時為什麼會落在那個位置；（B）Map ADT 的 put() 為什麼有 4 個 if/else 分支、每個分支什麼時候會被觸發，以及哪個才是真正的 collision。
A. Quadratic probing 全程追蹤（m = 11）
設定
雜湊函數 ：$h(\text{item}) = \text{item} \bmod 11$。Rehash ：$\text{rehash}(p, \text{skip}) = (p + \text{skip}) \bmod 11$，其中 skip 依序取 $1^2, 2^2, 3^2, 4^2, 5^2, \ldots = 1, 4, 9, 16, 25, \ldots$（這也是「quadratic」的由來）。插入順序 ：54, 26, 93, 17, 77, 31, 44, 55, 20（與教材 PDF 圖示同）。
Step 1：前六筆都直接落空槽
item item % 11 落點 slot 狀況
54 10 10 空 ✓ 26 4 4 空 ✓ 93 5 5 空 ✓ 17 6 6 空 ✓ 77 0 0 空 ✓ 31 9 9 空 ✓
此時表的狀態：
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）
嘗試 skip 計算位置 slot 內容 結果
1 $1^2 = 1$ (0+1) % 11 = 1 空 落 slot 1
Step 3：插 55（55 % 11 = 0，撞 77；之後又連撞 4 次）
嘗試 skip 計算位置 slot 內容 結果
1 $1^2 = 1$ (0+1) % 11 = 1 44 占用 2 $2^2 = 4$ (0+4) % 11 = 4 26 占用 3 $3^2 = 9$ (0+9) % 11 = 9 31 占用 4 $4^2 = 16$ (0+16) % 11 = 5 93 占用 5 $5^2 = 25$ (0+25) % 11 = 3 空 落 slot 3
關鍵
skip 序列是「連續完全平方數本身 」（$1, 4, 9, 16, 25$），不是累加 。每次都從原始 hash 位置 $h$ 起算，所以第 4 次跳到 $(0+16) \bmod 11 = 5$、第 5 次跳到 $(0+25) \bmod 11 = 3$：兩次都「跨過」了表的另一端。這正是 quadratic probing 能打散 linear probing 那種連續聚集（clustering）的原因。
Step 4：插 20（20 % 11 = 9，撞 31）
嘗試 skip 計算位置 slot 內容 結果
1 $1^2 = 1$ (9+1) % 11 = 10 54 占用 2 $2^2 = 4$ (9+4) % 11 = 2 空 落 slot 2
最終表狀態
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 搞混的地方）
先講清楚：什麼是 collision、什麼不是？
Collision 的判準是「hash 值 相同」，不是「key 相同」，千萬別搞反。
正式定義：兩個不同的 item 經過 hashFunction 後得到同一個 hash 值 （也就是 hash(k₁) == hash(k₂)，因此被映射到同一個 slot），這才叫 collision。判 collision 看的是「hash 值」這個運算結果，不是「key 本身」。
同一個 key 重複 put（如 h[77]="bird" 然後 h[77]="eagle"）：hash 值當然會相同，但兩次塞的是同一個 item ，只是更新同一個 entry，這不是 collision，也不會觸發任何 rehash 。collision 必須是「兩個不同 item 撞到同一格」。
狀況 兩個 item 的 hash 值 是同一個 key 嗎？ 這算 collision 嗎？ put 要做的事
情況一 相同（必然） 是（同 key 重複 put） 不是 直接覆寫舊值（字典「同 key 重新賦值」的語意） 情況二 相同 （hash 撞到了）否 （不同 key）是 啟動 rehash 探查，找下一個位置 情況三 不同 否 不是 各走各的 slot，互不相干
情況一、二 在程式裡都會「slots[hash] 已經有東西」，但只有情況二才是真 collision：差別就在那個被佔的 slot 裡放的 key 跟我「是不是同一個 item」。
課程強化版本的 put()：探查一圈就停
void put (int key, string value) { int start = hashFunction (key);
int position = start;
do {
if (slots[position] == -1 ) { // ① 或 ③：插入
slots[position] = key; data[position] = value; return ;
}
if (slots[position] == key) { // ② 或 ④：更新
data[position] = value; return ;
}
position = rehash (position);
} while (position != start);
throw overflow_error("hash table is full" );
}
教科書的基本版若只寫「找到空槽或同 key 才停」，滿表時會無限繞圈。課程 header 用起點作哨兵：完整探查一圈後明確丟出 overflow_error。
把 4 個分支按「碰撞 / 探查」分類
hash 第一次命中（無探查） rehash 探查之後
新增 entry （slot 是空的）① 起始槽直接插入 ③ 探查後遇空槽↑ 真正在「處理 collision」的路徑 覆寫已有同 key （不是 collision）② 起始槽直接更新 ④ 探查後遇同 key沿探查路徑找回既有 key
情境設定：4 步剛好走 4 個分支
h = HashTable(size=11)，hash = key % 11，rehash = (p+1) % 11。依序執行下列 4 條 h[key] = val，每一條剛好觸發一個分支：
步驟 操作 hash slots[hash] 走哪條分支 是 collision 嗎？ 為何
1 h[77]="bird"0 -1① 起始槽直接插入 — slot 0 空，直接寫入，不必探查 2 h[77]="eagle"0 77② 起始槽直接更新 否 slot 0 已有的 key 就是 77 → 同 key 重新賦值，直接覆寫，不啟動 rehash 3 h[44]="goat"0 77 (≠ 44)③ 探查後遇空槽 是 44 和 77 hash 值都是 0（不同 key、相同 hash） → collision → 探查到 slot 1 的空槽後插入 4 h[44]="lamb"0 77 (≠ 44)④ 探查後遇同 key 不是新的 collision 44 真正存於 slot 1；沿既有碰撞探查鏈找到同 key 後覆寫 value
每一步之後的表狀態（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 永遠只占一格」的保證。
結論
①、③ 是插入；②、④ 是同 key 更新。③ 會為新碰撞的 key 找空槽，④ 則沿既有碰撞鏈找回舊 key。判 collision 看的是「不同 item、相同 hash 值 」，不是「同一個 key 第二次來」。
每個探查位置都要檢查哪兩件事？
每到一格都依序判斷：
撞到 -1（空槽）停 → 落到分支 ③（新插入）
撞到 == key 停 → 落到分支 ④（覆寫）
不能只檢查空槽 ：否則「同 key 已在路徑上」時會繼續往下走，在另一格再寫一次，製造重複 key。也不能忘記「繞回起點」：滿表且 key 不存在時必須丟出
overflow_error，不能無限迴圈。
QUIZ · 自我檢測
自我檢測：搜尋、雜湊與排序 課程題庫 ch7 · 7 題
題目取自課程題庫（已譯為繁體中文），每個選項都有解說：選錯也點開看看為什麼錯。全對之後再往下翻詞彙卡。
Q1. 遞迴版二分搜尋傳入索引邊界，並令 midpoint = first + (last - first) / 2。對已排序 vector {3, 5, 6, 8, 11, 12, 14, 15, 17, 18} 找 16，依序比較哪些值？
12, 17, 15
18, 17, 15
11, 14, 17
11, 15, 17
Q2. 對 {5, 1, 4, 2, 8} 做遞增氣泡排序，完整跑完第一輪後 vector 是哪一個？
{1, 4, 2, 5, 8}
{1, 4, 2, 8, 5}
{1, 2, 4, 5, 8}
{5, 1, 4, 2, 8}
Q3. 大小為 13 的雜湊表，鍵 27 與 130 分別會對應到哪個索引位置？
1, 10
13, 0
1, 0
2, 3
Q4. 把這組鍵依序插入恰好 11 格的雜湊表：113, 117, 97, 100, 114, 108, 116, 105, 99，用線性探查解決碰撞。全部插完後，表的內容最接近下列哪一個？
100, __, __, 113, 114, 105, 116, 117, 97, 108, 99
99, 100, __, 113, 114, __, 116, 117, 105, 97, 108
100, 113, 117, 97, 14, 108, 116, 105, 99, __, __
117, 114, 108, 116, 105, 99, __, __, 97, 100, 113
Q5. 串列 [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40] 執行 mergesort。第 3 次遞迴呼叫時要排序的串列是下列哪一個？
[16, 49, 39, 27, 43, 34, 46, 40]
[21, 1]
[21, 1, 26, 45]
[21]
Q6. 串列 [14, 17, 13, 15, 19, 10, 3, 16, 9, 12] 執行 quicksort。第二次分割（partition）之後，串列內容是下列哪一個？
[9, 3, 10, 13, 12]
[9, 3, 10, 13, 12, 14]
[9, 3, 10, 13, 12, 14, 17, 16, 15, 19]
[9, 3, 10, 13, 12, 14, 19, 16, 15, 17]
Q7. 對有序串列 [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] 做循序搜尋，要判定 key 13 不在裡面，需要幾次比較？
10
5
7
6
CARDS · 關鍵詞彙卡
關鍵詞彙卡：點卡片翻面 題庫 ch7.json · 32 張
詞彙卡取自本章課程題庫，已譯為繁體中文，正面附英文原名。先看正面術語，心中默想定義再翻面對答案；洗牌後再過一輪，直到每張都能不假思索說出來。
🔀 洗牌
全部翻面
全部翻回