搜尋與排序演算法

先看懂：演算法分析的「比較」與「目標」 cppds §6.1–6.2

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

顏色語義（整頁通用）

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

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

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

有序版本：可以提前停止

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

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

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

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

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

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

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

其他常見的雜湊函數

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

應用：Map ADT (字典/HashTable)

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

氣泡排序：相鄰兩個比一比，大的往後送 cppds §7.2–7.3

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

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

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

插入排序：像整理撲克牌 cppds §7.5

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

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

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

講義原始實作（§7.6 Shell Sort）

外層 shellSort 維護當前 sublistCount（折半），對每個 posStart 呼叫 gapInsertionSort，把該子陣列做插入排序。

void gapInsertionSort(vector<int>& aList, int start, int gap) {
    for (unsigned i = start + gap; i < aList.size(); i += gap) {
        int curVal = aList[i];
        int curPos = i;
        while (curPos >= gap && aList[curPos - gap] > curVal) {
            aList[curPos] = aList[curPos - gap];
            curPos = curPos - gap;
        }
        aList[curPos] = curVal;
    }
}

void shellSort(vector<int>& aList) {
    int sublistCount = aList.size() / 2;
    while (sublistCount > 0) {
        for (int posStart = 0; posStart < sublistCount; posStart++) {
            gapInsertionSort(aList, posStart, sublistCount);
        }
        cout << "After increments of size " << sublistCount
             << " the list is ";
        printl(aList);
        sublistCount = sublistCount / 2;
    }
}

int main() {
    vector<int> aList = {5, 16, 20, 12, 3, 8, 9, 17, 19, 7, 11};
    shellSort(aList);
    printl(aList);
}

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

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

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

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

講義練習：讓 quicksort 支援降冪排序（Exercise 3）

講義的課後練習：替 quickSort 加一個 bool descending 參數，讓同一套程式碼既能升冪也能降冪。 解法漂亮在「幾乎什麼都不用改」：遞迴骨架原封不動，只有 partition 裡兩個內層 while 的比較方向要翻面。 升冪時 leftMark 找「大於 pivot 的」往右送；降冪時反過來找「小於 pivot 的」。

每個演算法需要什麼底層支援？ 課程補充

同樣的演算法，搬到不同的資料結構上效能可能截然不同，甚至根本跑不動。本節整理本章九個演算法各自能在哪些資料結構上有效執行，重點放在「為什麼某些演算法必須用 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 永遠只占一格」的保證。