深度探秘

搜尋到底在問什麼問題

搜尋是什麼

**搜尋（searching）**是「在一堆資料裡找出某一筆特定資料」的過程。最常見的回答只有兩種：在（True）或 不在（False）。

在 Python 裡，問「某個東西在不在清單裡」超簡單，用 in 就好：

>>> 15 in [3, 5, 2, 4, 1]
False
>>> 3 in [3, 5, 2, 4, 1]
True

但這行簡單的程式碼背後，其實藏著一套「真的去翻找」的流程。我們關心的，正是這個流程怎麼運作、以及不同做法有多快。

循序搜尋

當資料像清單一樣一個接一個排好（有 index 0、1、2…），它們之間就有「線性」或「循序」的關係。最直覺的找法叫循序搜尋（sequential search）：從第一個開始，一個一個往後比對，直到找到，或是翻完整串都沒找到。

def sequential_search(a_list, item):
    pos = 0
    found = False
    while pos < len(a_list) and not found:
        if a_list[pos] == item:
            found = True
        else:
            pos = pos + 1
    return found

變數 found 一開始是 False，一旦比中目標就變 True，迴圈也隨之停止。

生活妙喻

在沒分類的鞋櫃裡找一隻鞋

翻鞋櫃比喻

想像你家有一個完全沒分類的長鞋櫃，鞋子隨便亂塞。你要找一雙紅色球鞋：

• 你只能從最左邊那格開始，一格一格往右看。
• 看到就拿走（找到了，True）。
• 一路看到最後一格還是沒有，就確定家裡沒這雙（不在，False）。

這正是循序搜尋。重點在於：因為鞋子沒有任何順序，你沒辦法跳著找，只能老老實實一格一格看。

flowchart TD
    A[從第一格開始] --> B{這格是目標嗎}
    B -- 是 --> C[找到了 回傳 True]
    B -- 否 --> D{還有下一格嗎}
    D -- 有 --> E[移到下一格]
    E --> B
    D -- 沒有 --> F[翻完了 回傳 False]

實用超能力

排序過的清單能省一點力氣

算成本：用「比較次數」當尺

分析搜尋速度時，我們數的是比較的次數。假設清單有 $n$ 筆、且完全沒排序：

當 $n$ 很大時，係數（像 $\frac{1}{2}$）都可以忽略，所以循序搜尋的複雜度是 $O(n)$。

如果清單是排好序的？

假設清單由小到大排好。找 50 時，比到 54 就會發現：54 已經比 50 大，而後面只會更大，不可能再有 50 了，可以立刻停止！

def ordered_sequential_search(a_list, item):
    pos = 0
    found = False
    stop = False
    while pos < len(a_list) and not found and not stop:
        if a_list[pos] == item:
            found = True
        else:
            if a_list[pos] > item:
                stop = True
            else:
                pos = pos + 1
    return found

好處只出現在「找不到」的時候：平均只要看 $\frac{n}{2}$ 個就能確定不在。但整體仍是 $O(n)$——排序對循序搜尋幫助有限。

深度探秘

從中間下手，一次淘汰一半

聰明地利用排序

循序搜尋每比一次，最多只能排除一筆。但如果清單已經由小到大排好，我們可以聰明很多：二分搜尋（binary search）不從頭開始，而是先看正中間那筆。

比中間值之後有三種可能：

• 中間就是目標 → 找到，結束。
• 目標比中間小 → 它只可能在左半邊，右半邊（含中間）全部淘汰。
• 目標比中間大 → 它只可能在右半邊，左半邊（含中間）全部淘汰。

然後對剩下的那半邊重複同樣動作。每比一次就砍掉一半的搜尋範圍。

def binary_search(a_list, item):
    first = 0
    last = len(a_list) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if a_list[midpoint] == item:
            found = True
        else:
            if item < a_list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

生活妙喻

查字典找單字

查字典比喻

你不會從第一頁開始一頁一頁翻字典找「monkey」。你會直接翻到中間，看到「M」附近——欸，差不多到了；如果翻到「P」就往前一點、翻到「F」就往後一點。每翻一次，要找的範圍就縮小一半。

二分搜尋就是這套「翻字典」策略。前提是字典已經照字母排序——沒排序的字典根本沒辦法這樣翻。

flowchart TD
    A[看中間那一筆] --> B{中間就是目標嗎}
    B -- 是 --> C[找到了]
    B -- 目標比較小 --> D[只看左半邊]
    B -- 目標比較大 --> E[只看右半邊]
    D --> A
    E --> A

分治法

二分搜尋是**分治法（divide and conquer）**的經典範例：把大問題切成小問題、解小問題、再組合答案。每次都把問題縮小成「對半邊清單再做一次二分搜尋」，這正是一個遞迴呼叫。

實用超能力

為什麼快到只要 log n 次

算成本：能砍幾次一半？

從 $n$ 筆開始，每比一次就剩一半：

當砍到只剩 1 筆時就結束，也就是 $\frac{n}{2^i} = 1$，解出 $i = \log_2 n$。所以二分搜尋是 $O(\log n)$——資料量翻倍，也只多比一次！

切片版要小心

用遞迴搭配 Python 切片寫起來很漂亮：

def binary_search(a_list, item):
    if len(a_list) == 0:
        return False
    midpoint = len(a_list) // 2
    if a_list[midpoint] == item:
        return True
    elif item < a_list[midpoint]:
        return binary_search(a_list[:midpoint], item)
    else:
        return binary_search(a_list[midpoint + 1:], item)

但 Python 的切片是 $O(k)$，會讓它跑不到嚴格的對數時間。改用「傳起訖 index」就能解決。

提醒：對小清單來說，先排序再二分搜尋的成本不一定划算。要排一次、查很多次，排序的成本才被攤平。

深度探秘

用公式直接算出資料該放哪

從 O(log n) 再往前一步

二分搜尋靠『排序』達到 $O(\log n)$。雜湊（hashing）想做得更誇張：直接做到 $O(1)$——不論資料多少，查找都只要固定時間。

秘訣是：別再『找』資料，而是一開始就把每筆資料放到一個可以用公式算出來的位置。要查的時候，用同一條公式算出位置，直接去那一格看就好。

雜湊表與 slot

**雜湊表（hash table）**是一排編號的格子，每個格子叫 slot，從 0 開始編號。一開始全空（用 Python 的 None 表示）。下面是一個大小 $m = 11$ 的空雜湊表：

graph LR
    S0[slot0 空] --- S1[slot1 空] --- S2[slot2 空] --- S3[slot3 空] --- S4[slot4 空] --- S5[slot5 空]

雜湊函式

把資料對應到 slot 的那條公式，就是雜湊函式（hash function）。它吃進任何一筆資料，吐出一個介於 0 到 $m-1$ 的整數。

最基本的是餘數法（remainder method）：拿資料除以表的大小，取餘數當位置：

$$h(item) = item \bmod 11$$

例如把 54、26、93、17、77、31 放進大小 11 的表：

取餘數（模運算）幾乎一定會出現在所有雜湊函式裡，因為結果必須落在 slot 的編號範圍內。

生活妙喻

有規則的健身房置物櫃

置物櫃比喻

想像一間健身房有 11 個置物櫃（編號 0～10）。規則是：用你的會員號碼除以 11，餘數就是你的櫃號。

• 你不需要一個一個櫃子去拉門找東西。
• 心算一下會員號 % 11，直接走到那個櫃子，一步到位。

這就是雜湊：位置不是用找的，是用算的。算位置只要一瞬間，所以查找是 $O(1)$。

字串也能雜湊

字串怎麼算？把每個字元的序數（ord）加起來再取餘數。例如『cat』：

>>> ord('c'), ord('a'), ord('t')
(99, 97, 116)
# 99 + 97 + 116 = 312, 312 % 11 = 4

def hash(a_string, table_size):
    sum = 0
    for pos in range(len(a_string)):
        sum = sum + ord(a_string[pos])
    return sum % table_size

有趣的是：字母相同順序不同的字（anagram，如 cat 與 act）會得到相同雜湊值。想避免可以把『字元位置』當權重，讓順序也參與計算。

實用超能力

好的雜湊函式長什麼樣，碰撞又是什麼

完美雜湊與它的代價

若一個雜湊函式能讓每筆資料都對應到獨一無二的 slot，就叫完美雜湊函式（perfect hash function）。但對任意資料，沒有系統化的方法保證做出完美雜湊。

一個笨方法是把表開到夠大、每個可能的值都有專屬格子。但若資料是九位數的身分證號，這要將近十億格——存 25 個學生卻開十億格，太浪費了。

所以我們的目標是：碰撞少、好算、分布均勻。

幾種雜湊函式

• 折疊法（folding）：把資料切成等長小段相加再取餘。例如電話 436-555-4601 切成 43,65,55,46,01，相加 210，$210 \bmod 11 = 1$。
• 平方取中法（mid-square）：先平方，再取中間幾位數。例如 $44^2 = 1936$，取中間兩位 93，$93 \bmod 11 = 5$。

碰撞

問題來了：如果 44 也要進來，$44 \bmod 11 = 0$，但 77 已經佔了 slot 0。兩筆以上資料算到同一格，就叫碰撞（collision）。碰撞會破壞 $O(1)$ 的美夢，下一節專門處理它。

雜湊函式也不能太複雜——如果算位置比直接做循序或二分搜尋還久，就本末倒置了。

深度探秘

兩筆資料想擠同一格怎麼辦

碰撞一定會發生

上一節我們看到：當 44 想進來時，$44 \bmod 11 = 0$，但 slot 0 已經被 77 佔走了。兩筆資料算到同一格，就是碰撞（collision）。除非用完美雜湊（通常做不到），否則碰撞遲早會發生，所以一定要有一套處理規則，這就叫解決碰撞（collision resolution）。

開放定址法 + 線性探測

一種思路是：撞到了就往後找下一個空格。從原本的位置開始，一格一格往後看，遇到第一個空的就放進去（必要時繞回 slot 0 形成一個圈）。這種『找下一個開放的地址』叫開放定址法（open addressing）；一格一格地找則叫線性探測（linear probing）。

以資料 54,26,93,17,77,31,44,55,20 為例（表大小 11）：

• 44 想進 slot 0，但被 77 佔了 → 往後到 slot 1（空），放下。
• 55 也想進 slot 0 → 往後找到 slot 2（空），放下。
• 20 算到 slot 9（被 31 佔），往後看 10、0、1、2 都滿，最後在 slot 3 找到空位。

flowchart TD
    A[算出原始 slot] --> B{這格空嗎}
    B -- 空 --> C[放進去]
    B -- 滿 --> D[往後看下一格 必要時繞回 0]
    D --> B

生活妙喻

客滿的停車場找車位

停車場比喻

想像一個環形停車場，你的『指定車位』是用車牌算出來的。但你開到時發現有人停了——線性探測就像：繞著往前一格一格看，停進第一個看到的空位。

搜尋時也得用同一套規則：要找 20，先算到 slot 9，發現是 31 不是 20。你不能直接說『不在』，因為它可能因為碰撞被擠到後面去了。所以得從 slot 10 開始往後找，直到找到 20、或遇到一個空格（空格代表後面不可能再有它了）。

群聚問題

線性探測有個毛病叫群聚（clustering）：很多資料撞在同一個雜湊值附近時，會把周圍格子塞成一坨。這一坨會連累後來的資料（像 20 就被迫繞過一整坨才找到位置）。

實用超能力

再雜湊、二次探測與鏈結法

再雜湊：撞了之後跳著找

撞到後找下一格的通用動作叫再雜湊（rehashing）。線性探測的再雜湊是：

$$rehash(pos) = (pos + 1) \bmod size$$

為了打散群聚，可以改成『加 3』跳著找：

$$rehash(pos) = (pos + 3) \bmod size$$

一般化就是 $rehash(pos) = (pos + skip) \bmod size$。

注意：skip 的大小要能讓所有 slot 終究都被走訪到，否則表會有一部分永遠用不到。常建議把表大小設成質數，這也是我們一直用 11 的原因。

二次探測

**二次探測（quadratic probing）**不用固定 skip，而是用一連串完全平方數當間隔：第一次 $h$，接著 $h+1, h+4, h+9, h+16 \ldots$。這能進一步減少群聚。

鏈結法

另一條完全不同的路是鏈結法（chaining）：讓每個 slot 不只放一筆，而是掛一整串（一條鏈）。撞到就掛到同一格的鏈上。

graph LR
    Slot0[slot0] --> A77[77] --> A44[44] --> A55[55]
    Slot4[slot4] --> B26[26]

查找時先算 slot，再在那一格的鏈上做一次小搜尋。平均而言每條鏈很短，所以還是很有效率。

深度探秘

Map 抽象資料型別與雜湊實作

Map 是什麼

Python 最好用的集合之一是字典（dictionary），它存的是鍵-值對（key-value pair）：用 key 查出對應的 value。這個概念抽象起來就叫 map。

**Map 抽象資料型別（ADT）**是一群 key 對 value 的對應，key 不重複（一對一）。主要操作：

• Map()：建立空 map。
• put(key, val)：放入一對；key 已存在就更新 value。
• get(key)：依 key 取出 value，沒有就回 None。
• del、len()、in：刪除、計數、判斷是否存在。

字典最大的好處就是『給 key 能極快查到 value』，而雜湊表正好能提供接近 $O(1)$ 的查找，是實作 map 的理想底層。

用兩個平行清單實作

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

slots 存 key、data 存對應的 value，位置一一對應：key 在 slots 的第幾格，它的 value 就在 data 的第幾格。表大小設質數 11 讓解決碰撞更有效率。

生活妙喻

put 與 get 像置物櫃存取包裹

put：放包裹

put 先用雜湊函式算出 key 該在哪格：

• 那格是空的 → 直接放 key 與 data。
• 那格已經是同一個 key → 更新 data（取代舊值）。
• 那格被別的 key 佔了（碰撞）→ 用 rehash 一格格往後找，直到找到空格或同一個 key。

def put(self, key, data):
    hash_value = self.hash_function(key, len(self.slots))
    if self.slots[hash_value] == None:
        self.slots[hash_value] = key
        self.data[hash_value] = data
    else:
        if self.slots[hash_value] == key:
            self.data[hash_value] = data  # 取代
        else:
            next_slot = self.rehash(hash_value, len(self.slots))
            while self.slots[next_slot] != None and self.slots[next_slot] != key:
                next_slot = self.rehash(next_slot, len(self.slots))
            if self.slots[next_slot] == None:
                self.slots[next_slot] = key
                self.data[next_slot] = data
            else:
                self.data[next_slot] = data  # 取代

get：取包裹

get 同樣先算起始格，沿 rehash 往後找；關鍵是用 position == start_slot 判斷『繞了一整圈回到起點』，避免無限迴圈——繞回起點代表找遍了都沒有。

flowchart TD
    A[算出起始 slot] --> B{這格是目標 key 嗎}
    B -- 是 --> C[回傳對應的 data]
    B -- 否且非空 --> D[rehash 到下一格]
    D --> E{繞回起點了嗎}
    E -- 是 --> F[找遍了 回傳 None]
    E -- 否 --> B
    B -- 遇到空格 --> F

再用 __getitem__ 與 __setitem__ 重載，就能像字典一樣用 h[key] 存取。

實用超能力

負載因子如何決定查找成本

負載因子 λ

理想上雜湊查找是 $O(1)$，但碰撞會讓比較次數變多。分析雜湊最關鍵的數字是負載因子（load factor）：

$$\lambda = \frac{\text{資料筆數}}{\text{表大小}}$$

• $\lambda$ 小：表很空，碰撞少，資料多半就在它該在的格子。
• $\lambda$ 大：表快滿了，碰撞多，要找空格或追鏈更費力。

平均比較次數公式

開放定址 + 線性探測：

• 成功查找約 $\frac{1}{2}\left(1 + \frac{1}{1-\lambda}\right)$
• 失敗查找約 $\frac{1}{2}\left(1 + \left(\frac{1}{1-\lambda}\right)^2\right)$

鏈結法：

• 成功查找約 $1 + \frac{\lambda}{2}$
• 失敗查找約 $\lambda$

直覺解讀

你會發現：$\lambda$ 越接近 1（表越滿），$\frac{1}{1-\lambda}$ 就爆炸性變大，查找急遽變慢。這告訴我們一個實務重點：雜湊表不該裝太滿，通常在負載因子超過某門檻（例如 0.7）時就該擴充表的大小，重新雜湊，才能維持接近 $O(1)$ 的效能。

深度探秘

相鄰兩兩比較、看誰該往後

排序在做什麼

**排序（sorting）**是把一堆資料依某種順序排好，例如數字由小到大、單字依字母。分析排序時我們關心兩個動作：**比較（compare）兩個值誰大誰小，以及交換（exchange / swap）**把放錯位置的兩個值對調。交換是相對昂貴的動作。

氣泡排序

**氣泡排序（bubble sort）**會對清單做很多輪（pass）。每一輪從頭開始，比較相鄰的兩個元素，順序不對就交換。每跑完一輪，就會把這輪最大的值『推』到它最終的位置——就像大泡泡慢慢浮到水面。

$n$ 個元素第一輪要比 $n-1$ 對，第二輪因為最大值已就位只剩 $n-2$ 對……總共要 $n-1$ 輪。

def bubble_sort(a_list):
    for pass_num in range(len(a_list) - 1, 0, -1):
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                temp = a_list[i]
                a_list[i] = a_list[i + 1]
                a_list[i + 1] = temp

在 Python 裡還能用同時指定一行搞定交換：a, b = b, a。

生活妙喻

汽水裡的大泡泡浮上來

泡泡浮起來

想像一排高矮不一的人站著，你規定：從左邊開始，相鄰兩人比身高，高的往右站。一路比到底，最高的人就會被一路換到最右邊。第二輪再做一次，第二高的就站到倒數第二……每一輪都有一個『最大泡泡』浮到正確位置。

flowchart TD
    A[從最左邊開始] --> B{相鄰兩個 左邊比右邊大嗎}
    B -- 是 --> C[交換兩者]
    B -- 否 --> D[不動]
    C --> E[往右移一格]
    D --> E
    E --> F{這一輪比完了嗎}
    F -- 沒有 --> B
    F -- 完成 --> G[最大值已就定位 進入下一輪]

為什麼說它『浪費』

氣泡排序常被認為最沒效率，因為它會在『還不知道最終位置』時就不斷交換，做了很多白工。但它有個獨門好處，下一步揭曉。

實用超能力

為何是 O(n²) 與 short bubble 的小聰明

算成本

不管資料怎麼排，氣泡排序都要做 $n-1$ 輪。各輪比較次數是 $n-1, n-2, \ldots, 1$，加起來是前 $n-1$ 個整數的總和：

$$\sum_{i=1}^{n-1} i = \frac{1}{2}n^2 - \frac{1}{2}n$$

所以氣泡排序是 $O(n^2)$。最好情況（已排序）不需任何交換，最差情況每次比較都要交換。

Short bubble 的小聰明

氣泡排序有個別人沒有的能力：如果某一輪完全沒有發生交換，代表清單已經排好了，可以提早收工。這個改良叫 short bubble：

def short_bubble_sort(a_list):
    exchanges = True
    pass_num = len(a_list) - 1
    while pass_num > 0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                exchanges = True
                a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i]
        pass_num = pass_num - 1

對『幾乎已排好』的清單，short bubble 能很快察覺並停下，這時它反而有優勢。

深度探秘

先找出最大值，最後才動手交換

選擇排序的改良點

**選擇排序（selection sort）**是氣泡排序的改良版。它的核心想法是：每一輪只交換一次。

做法是：在一輪掃描中先用眼睛找出最大值在哪裡（記住它的位置），整輪掃完之後，才把這個最大值和該輪最後一格交換一次，讓它一步到位。

和氣泡排序一樣，第一輪後最大值就位、第二輪後次大值就位……同樣需要 $n-1$ 輪。

def selection_sort(a_list):
    for fill_slot in range(len(a_list) - 1, 0, -1):
        pos_of_max = 0
        for location in range(1, fill_slot + 1):
            if a_list[location] > a_list[pos_of_max]:
                pos_of_max = location
        temp = a_list[fill_slot]
        a_list[fill_slot] = a_list[pos_of_max]
        a_list[pos_of_max] = temp

注意內層迴圈只更新 pos_of_max（記位置），完全不交換；交換只在外層、每輪一次。

生活妙喻

選秀挑出最高的人再請他站定位

選秀比喻

想像你要幫一排人由矮到高排好。氣泡排序像『相鄰兩人不順眼就一直互換』，換個不停。

選擇排序更冷靜：你先用眼睛掃過所有人，記住『最高的是第幾個』，掃完才請他一個人走到隊伍最後。下一輪再掃剩下的人，找出次高的請他站倒數第二……

你看的次數（比較）跟氣泡排序一樣多，但你只請人移動最少的次數——每輪頂多請一個人換位置。

flowchart TD
    A[從未排序區開始掃描] --> B[記住目前看到的最大值位置]
    B --> C{還有下一個嗎}
    C -- 有 --> D[比較並更新最大值位置]
    D --> C
    C -- 沒有 --> E[把最大值與本輪末格交換一次]
    E --> F[進入下一輪 範圍縮小一格]

實用超能力

比較一樣多、交換卻少很多

比較次數：和氣泡一樣

選擇排序的比較次數和氣泡排序相同，都是把前 $n-1$ 個整數加起來：

$$\sum_{i=1}^{n-1} i = \frac{1}{2}n^2 - \frac{1}{2}n$$

所以時間複雜度仍是 $O(n^2)$。

但交換次數差很多

關鍵差別在交換：選擇排序每輪最多只交換一次，總共最多 $n-1$ 次。而氣泡排序在過程中可能交換非常多次。

書中那個 9 元素的例子：

由於交換是昂貴動作，選擇排序在實測中通常跑得比氣泡排序快。

重點觀念：兩個演算法雖然同屬 $O(n^2)$，實際速度仍可能有差，因為大 O 忽略了『比較』與『交換』成本不同這件事。

深度探秘

維護一段已排序子清單

插入排序的核心

**插入排序（insertion sort）**雖然也是 $O(n^2)$，但做法很不一樣。它的關鍵是：在清單前段維護一段『已經排好序』的子清單，然後一次拿一個新元素，把它『插回』這段子清單的正確位置，讓已排序子清單長大一格。

一開始我們假設『只有第 0 格』本身就是已排序的子清單。接著從 index 1 到 $n-1$，每個元素都拿去和前面已排序的子清單比對。

def insertion_sort(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        while position > 0 and a_list[position - 1] > current_value:
            a_list[position] = a_list[position - 1]
            position = position - 1
        a_list[position] = current_value

位移，不是交換

注意 a_list[position] = a_list[position - 1] 這行是位移（shift）：把比 current_value 大的元素往右挪一格，騰出空間，最後才把 current_value 放進那個空位。這跟前面那種完整『交換』不同。

生活妙喻

整理手上的撲克牌

撲克牌比喻

打牌時你抓牌、整理手牌的方式，幾乎就是插入排序：

• 你手上左邊那幾張已經排好了。
• 抓到一張新牌，你從右往左看，把比它大的牌往右推，騰出空檔。
• 推到遇到比它小的牌（或推到最左）就停，把新牌插進那個空檔。

第五張牌插入的細節：已排好的是 17,26,54,77,93，現在要插 31。先比 93（往右推）、再比 77、54（都往右推），比到 26 比 31 小，停！把 31 放進空出的位置。現在已排好六張。

flowchart TD
    A[拿起下一個新元素] --> B{它左邊那張比它大嗎}
    B -- 是 --> C[把左邊那張往右移一格]
    C --> B
    B -- 否 或已到最左 --> D[把新元素放進空出的位置]
    D --> E[已排序子清單長大一格]

實用超能力

位移比交換便宜、近乎排好時超快

算成本

最差情況的比較次數一樣是前 $n-1$ 個整數的總和，所以是 $O(n^2)$。但最好情況（清單已排好）每輪只要比較一次就發現不用移動，這時接近 $O(n)$！

位移比交換便宜

一個常被忽略的重點：一次位移大約只要一次指定（assignment），而一次完整交換要三次指定。所以位移大約只花交換三分之一的工。這讓插入排序在實測中表現往往相當好。

什麼時候特別適合

• 資料量小。
• 資料幾乎已經排好（只有少數元素位置不對）。

這兩種情況下，插入排序又快又簡單，也是後面『希爾排序』的基礎。

深度探秘

用間隔把清單拆成多個子清單

希爾排序的巧思

希爾排序（shell sort）又叫『遞減增量排序』，是插入排序的升級版。它的獨門巧思在於怎麼挑子清單：不是把連續相鄰的元素分成一組，而是用一個間隔（gap，又叫 increment） $i$，每隔 $i$ 個取一個元素組成子清單，再對每個子清單做插入排序。

例如 9 個元素、間隔 3，就會分出 3 個子清單（位置 0,3,6／1,4,7／2,5,8）。把這幾個子清單各自排好之後，整串雖然還沒完全排好，但每個元素都被搬到更接近它最終位置的地方了。

接著把間隔縮小（例如從 $\frac{n}{2}$、$\frac{n}{4}$……一路減到 1），最後一次間隔為 1 的排序，其實就是一次標準的插入排序。

生活妙喻

搬家先粗分區域再細排

搬家比喻

想像你要把一大堆書照編號排好。如果一開始就一本一本相鄰比較（純插入排序），離家很遠的書要一格一格慢慢挪過來，超累。

希爾排序的策略像搬家先『大跳躍歸位』：

• 先用大間隔：把書粗略丟到『大概對的那一區』，遠方的書一次就跨很大步靠近目標。
• 再用小間隔：在小範圍內微調。
• 最後間隔 1：做一次細部插入排序，但因為大家都已經很接近定位，幾乎不用再挪。

flowchart TD
    A[大間隔 把元素大步搬到大概位置] --> B[縮小間隔 在較小範圍微調]
    B --> C[間隔縮到 1 做一次插入排序]
    C --> D[因為已近乎排好 這次幾乎不用搬]

關鍵直覺：早期的大間隔排序讓清單『越來越接近排好』，使最後那次插入排序變得超輕鬆。

實用超能力

程式碼與介於 O(n) 到 O(n²) 的效能

程式碼

def shell_sort(a_list):
    sublist_count = len(a_list) // 2
    while sublist_count > 0:
        for start_position in range(sublist_count):
            gap_insertion_sort(a_list, start_position, sublist_count)
        sublist_count = sublist_count // 2

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

gap_insertion_sort 其實就是一個『步幅為 gap』的插入排序——把原本的 -1 換成 -gap。

效能

你可能會想：最後一步既然是完整插入排序，怎麼可能比插入排序快？關鍵就是：前面幾輪已經把清單變得『更有序』，最後那次插入排序需要的比較與位移都很少。

希爾排序的完整分析很複雜，但大致落在 $O(n)$ 與 $O(n^2)$ 之間。若改用特定的間隔序列，例如 $2^k - 1$（1, 3, 7, 15, 31…），可達到約 $O(n^{3/2})$。間隔的選擇正是希爾排序效能的關鍵。

深度探秘

分治法：切到剩一個，再合併回去

合併排序的兩個動作

合併排序（merge sort）是用分治法改善排序效能的第一個例子。它是遞迴的，分兩個動作：

1. 分（split）：如果清單長度大於 1，就從中間切成左右兩半，對兩半各自遞迴呼叫 merge_sort。
2. 合（merge）：當兩半都排好後，把兩個已排序的小清單合併成一個更大的已排序清單。

基底條件（base case）是：清單空的或只有一個元素，依定義就已經排好，直接返回。

def merge_sort(a_list):
    if len(a_list) > 1:
        mid = len(a_list) // 2
        left_half = a_list[:mid]
        right_half = a_list[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        # 合併 left_half 與 right_half 回 a_list
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                a_list[k] = left_half[i]; i += 1
            else:
                a_list[k] = right_half[j]; j += 1
            k += 1
        while i < len(left_half):
            a_list[k] = left_half[i]; i += 1; k += 1
        while j < len(right_half):
            a_list[k] = right_half[j]; j += 1; k += 1

清單長度是奇數也沒關係，左右兩半最多差一個。

生活妙喻

兩疊已排好的考卷合成一疊

合併兩疊考卷

『合併』這個動作最好懂：想像你和同學各拿著一疊已經按分數由低到高排好的考卷，要合成一大疊排好的。

你們同時看各自最上面那張，誰的分數小就先放到新疊，然後那個人翻下一張。一直比下去，直到其中一疊先發完，再把另一疊剩下的整批接上去。因為兩疊原本就排好了，這樣合出來的大疊也是排好的。

flowchart TD
    A[原始清單] --> B[切成左半與右半]
    B --> C[左半再遞迴切到剩一個]
    B --> D[右半再遞迴切到剩一個]
    C --> E[兩兩合併成排好的小清單]
    D --> E
    E --> F[一層層合併成完整排好的清單]

切的時候像把考卷不斷對半分到每人手上只剩一張；合的時候再一層層比較合回去。

實用超能力

穩定的 O(n log n) 與空間代價

算成本

合併排序有兩個過程要算：

• 分：把清單對半切，能切 $\log n$ 次（就像二分搜尋）。
• 合：每一層合併都要碰過全部 $n$ 個元素。

所以是『$\log n$ 層 × 每層 $n$ 個工』：

$$O(n \log n)$$

更棒的是，不論輸入長怎樣，合併排序都保證是 $O(n \log n)$——這是它最大的賣點之一。

代價：額外空間

天下沒有白吃的午餐。left_half = a_list[:mid] 這類切片會複製出新清單，需要額外記憶體來存兩半。當資料很大時，這個額外空間可能成為問題。

另外，因為切片是 $O(k)$，嚴格來說要改成『傳起訖 index』才能保證真正的 $O(n \log n)$，但核心觀念不變。

一句話總結

合併排序：速度穩、保證 $O(n \log n)$，但要用記憶體換。

深度探秘

選一個基準值，把資料分成左小右大

快速排序的目標

快速排序（quick sort）同樣用分治法，想要拿到合併排序的速度優勢，卻不需要額外的記憶體空間。代價是：它不保證每次都對半切，切歪了效能會變差。

核心步驟：

1. 選一個基準值（pivot value）（這裡簡單地用第一個元素）。
2. 透過 partition（分割） 把比 pivot 小的移到左邊、比 pivot 大的移到右邊，找出 pivot 的最終位置——稱為分割點（split point）。
3. 對分割點左右兩半遞迴做快速排序。

def quick_sort(a_list):
    quick_sort_helper(a_list, 0, len(a_list) - 1)

def quick_sort_helper(a_list, first, last):
    if first < last:
        split_point = partition(a_list, first, last)
        quick_sort_helper(a_list, first, split_point - 1)
        quick_sort_helper(a_list, split_point + 1, last)

pivot 一旦放到分割點，它就永遠定位了，因為左邊全比它小、右邊全比它大。

生活妙喻

用一個身高基準把人分成兩排

分邊比喻

想像體育老師要排隊。他隨手指定一個同學當基準（pivot），然後喊：『比他矮的站左邊、比他高的站右邊！』喊完之後，這位基準同學站的位置就是他最終該站的位置（左邊都比他矮、右邊都比他高）。

接著對『左邊那群』和『右邊那群』各自再玩一次同樣的遊戲，遞迴下去，整排就排好了。

partition 怎麼動手

用兩個標記 left_mark（從左往右）和 right_mark（從右往左）夾擊：

• left_mark 往右走，直到遇到一個比 pivot 大的值（這個該去右邊卻待在左邊）。
• right_mark 往左走，直到遇到一個比 pivot 小的值。
• 兩邊都卡住時，交換這兩個放錯邊的值，繼續夾。
• 當 right_mark 跑到 left_mark 左邊時停止，right_mark 就是分割點，把 pivot 換過去定位。

flowchart TD
    A[選第一個元素當 pivot] --> B[left_mark 右移找比 pivot 大的]
    B --> C[right_mark 左移找比 pivot 小的]
    C --> D{兩標記交錯了嗎}
    D -- 否 --> E[交換這兩個放錯邊的值]
    E --> B
    D -- 是 --> F[把 pivot 換到 right_mark 即分割點]

實用超能力

平均 O(n log n)、最差 O(n²) 與 median of three

算成本

• 平均/理想：若每次 partition 都切在中間，會有 $\log n$ 層，每層檢查全部 $n$ 個元素，得 $O(n \log n)$，而且不用像合併排序那樣多花記憶體。
• 最差：若 pivot 每次都選到最小或最大值，切出來會是『0 個』和『$n-1$ 個』，極度不平衡，退化成 $O(n^2)$，還要背負遞迴開銷。

median of three

為了避免切歪，可以用三數取中（median of three）選 pivot：看第一、中間、最後三個元素，取它們的中位數當 pivot。這在『原始資料本來就有點排序』時特別有用，能挑到比較像『中間值』的 pivot，降低退化成 $O(n^2)$ 的機會。

一句話：快速排序通常很快又省空間，但最怕 pivot 選得爛——所以怎麼選 pivot 很重要。