選修單元 C ECCH6：檢索與排序｜線性檢索、對分檢索、排序法

導讀學習地圖：先「排序」再「檢索」？還是相反？

1) 你要解決的兩類問題

檢索（search）：在一堆資料中，找出「目標值」是否存在、在甚麼位置。
排序（sort）：把資料按某個規則（例如由小至大）重新排列，令資料更易閱讀或更易處理。

很多時候，排序不是「為了好看」，而是為了讓之後的對分檢索或其他處理更有效率。

2) 為何要學不同方法？

不同方法在「時間」與「記憶體」的取捨不同：

有些方法易理解但較慢（例如冒泡排序法）。
有些方法較快但概念較深（例如合併排序法、快速排序法）。
有些方法對資料狀態很敏感（例如插入排序法對「幾乎已排序」的資料特別快）。

3) 本頁你需要帶走的能力

能用自己的話清楚描述每一種方法的步驟（不是只背名字）。
能判斷在某個情境下，哪一種方法較合適（例如資料是否已排序、資料量大小）。
能看懂偽代碼，並用 Python 寫出基本版本。

核心提醒：本頁以陣列作為主要資料結構示例（Python 以 list 示範）。因為陣列支援「按索引直接存取」，最能清楚展示檢索與排序的流程。

小提醒：while / do while 的條件是「繼續循環」；repeat until 的條件是「停止循環」。

甚麼是檢索？

重點

「檢索」的核心任務：在一批資料中找出目標是否存在，以及位置（索引）或相關資料。
同一個問題可以有不同算法：有些重視「易做、穩陣」，有些重視「大量查找時更快」。
檢索算法的選擇，往往取決於：資料是否已排序、資料量、以及你需要查找的次數。
本課程的核心檢索算法：線性檢索與對分檢索；其餘會以增潤形式介紹（已清楚標示）。

定義

檢索是指：在一個資料集合（例如一個陣列）中，根據「目標條件」尋找資料。最常見的情況是：在陣列 A 中找目標值 target。

檢索的輸入／輸出可這樣理解：

輸入：資料（例如陣列 A）＋目標（例如 target）
輸出：目標的位置（索引）、或「未找到」（常用 -1 代表）

很多題目其實是在問：你能否清楚說出「檢索流程」與「找不到時怎樣處理」。

原理／運作

不同算法的差異，主要在於：

每一步能排除多少可能（例如對分檢索每次排除一半）
是否需要前提（例如對分檢索必須已排序）
做一次 vs 做很多次（例如用雜湊建立索引後，可重複快速查找）

簡單比較（以一般情況計）：

算法	是否需要已排序	典型時間	適用情境
線性檢索	否	最壞 O(n)	資料不大／不想先排序／只找一次
對分檢索	是	最壞約 O(log n)	資料已排序，且要快速定位
雜湊檢索（增潤）	否（但需建立雜湊結構）	平均約 O(1)	大量「查是否存在」的查找
插值檢索（增潤）	是（且分佈較均勻）	某些情況可快於對分檢索	已排序且分佈接近均勻的數值資料

檢索不是「背誦名字」：你要先判斷資料是否已排序、是否需要反覆查找，才選擇合適算法。

例子

假設你要在 100 個數字中找一個目標值： 線性檢索最壞要比 100 次； 對分檢索大約只需比 7 次左右（因為 2^7 = 128）。

如果你要做的不是「找一次」，而是「找很多次」（例如每次輸入一個目標值都要查一次），那麼雜湊檢索會先建立索引，之後每次查找通常更快。

想法：一次性成本（建立／排序） vs 每次查找成本。

比較

本頁面會把檢索算法分成三類，方便你掌握重點：

課程內：線性檢索、對分檢索（需要能清楚寫出流程與追蹤表）
增潤：雜湊檢索、插值檢索（認識原理與應用情境，提升解題視野）

頁面中已用「【增潤】」清楚標示增潤內容。

常見錯誤

忽略前提：用對分檢索處理未排序資料，結果自然不可靠。
忽略輸出：題目問「索引」，卻傳回「值」；或找不到時未傳回 -1。
只看 Big‑O：忘記實際上要考慮排序／建立索引的成本，以及是否需要額外記憶體。

改正方法：答題時先說「前提」，再說「流程」，最後補「找不到怎樣做」。

在日常生活中，「檢索」其實無處不在：例如在通訊錄中找某位聯絡人、在檔案夾中找某份文件、在名冊中找某位同學。這些情境的共同點是：你有一堆資料，而你需要在合理時間內找到目標。

在電腦科學中，檢索的關鍵不只是「能不能找到」，而是「需要多少步」。當資料量很小時，任何方法看起來都差不多；但當資料量變大（例如由 10 增加到 100、1000），不同算法的差距就會非常明顯。

因此，你學檢索算法時，請特別留意兩件事：第一，算法有沒有前提（例如資料是否已排序）；第二，你是「找一次」還是「找很多次」。只要你能把這兩點說清楚，你就能在不同題目中選擇合適的方法。

線性檢索（Linear Search）

重點

由陣列第一個元素開始，逐個比較，直到找到目標或到達尾端。

Python 小練習：印出每次比較（for loop）

把 target 改成其他值，再觀察程式會在第幾次比較時停止。
A = [7, 2, 9, 4, 2, 5, 1, 8, 6, 3] target = 4 count = 0 for i in range(len(A)): count += 1 print(f"第 {count} 次比較：A[{i}] = {A[i]}") if A[i] == target: print("✅ 找到！索引 =", i) break print("總比較次數 =", count)
不需要資料已排序；因此在資料無序或資料量不大時非常常用。

Python 小練習：用 while loop 寫線性檢索

請先理解：即使 A 是無序，線性檢索仍然能找到目標（只是可能要比較較多次）。
def linear_search(A, target): i = 0 while i < len(A): if A[i] == target: return i i += 1 return -1 A = [10, 3, 7, 3, 8] # 無序都可以 print("找 7 =>", linear_search(A, 7)) print("找 999 =>", linear_search(A, 999))
最壞情況下需要比較 n 次（n = 元素數量），所以效率會隨資料量增加而明顯下降。

Python 小練習：驗證「target 不存在」時要比較 n 次

把 A 改長一點（例如 1..100），再看比較次數是否等於 len(A)。
A = list(range(1, 11)) # 1..10 target = 999 # 不存在 count = 0 for x in A: count += 1 if x == target: break print("n =", len(A)) print("target 不存在時，比較次數 =", count)

定義

線性檢索（linear search）是一種最直接的檢索方法：從資料的起點開始，按固定方向逐一檢查每個元素是否等於目標值。

輸入／輸出通常是：

輸入：一個陣列 A、一個目標值 target
輸出：目標值在陣列中的位置（索引），或「未找到」（常用 -1 表示）

一句概括：由頭到尾逐一查找，找到即停止；若找不到，則回報「未找到」。

原理／運作

設 i = 0，由第 0 個元素開始。
比較 A[i] 與 target：

若相等：立即傳回 i（這叫早停）。
若不相等：i 加 1，繼續下一個元素。

如果 i 已到尾端仍未找到：傳回 -1。

線性檢索的「快」靠的是運氣（目標出現在前面），不是靠「每一步能排除大量可能」。

例子

陣列：A = [7, 2, 9, 4, 2, 5, 1, 8, 6, 3]，目標：target = 4

i	A[i]	是否等於 4？	結果
0	7	否	繼續
1	2	否	繼續
2	9	否	繼續
3	4	是	傳回索引 3

如果目標是最後一個元素或根本不存在，就會把整個陣列掃完。

比較

線性檢索：不需要排序；最壞情況比較 n 次。
對分檢索：需要資料已排序；每次比較可排除一半範圍；最壞情況比較約 log₂(n) 次。

何時用線性檢索？

資料量不大，或只需偶爾找一次。
資料未排序，而且排序成本不值得。
資料結構不方便做「中間存取」（例如線性鏈表）。

常見錯誤

索引越界：把迴圈寫成 i ≤ n，導致讀到不存在的位置。
未處理「找不到」：程式沒有傳回 -1，令呼叫者誤以為找到。
混淆「值」與「位置」：傳回 A[i]（值）而不是 i（索引）。
忘記早停：找到後仍繼續掃描，浪費時間。

改錯口訣：迴圈範圍、傳回內容、未找到處理三樣都要檢查。

線性檢索之所以容易理解，是因為它模仿了人類「逐個檢查」的習慣：例如在一列名字中找某位同學，你會從第一個名字開始向下掃，直到看到目標名字才停下來。在程式中，這種做法最直接，亦最不容易出錯。

但線性檢索的代價也很明顯：如果資料很多，而目標又經常出現在後面，或根本不存在，程式就需要做大量無效比較。因此，當資料量變大，或者你需要重複檢索很多次時，便要考慮是否值得先把資料排序，再使用更有效率的對分檢索。

在學習檢索時，你不只要記住步驟，更要培養「比較次數感」：當 n 變成 10 倍，線性檢索最壞情況比較次數也會接近 10 倍增加，這就是時間複雜度帶來的直觀影響。

互動示範：線性檢索（可自行生成資料）

你可以自行設定「數據項目數量」及「數值範圍」，按「生成資料」後，再用「下一步」觀察每次比較的位置（當前索引會被標記）。

圖像化例子：線性檢索的逐步比較

目標：在陣列 [7, 2, 9, 4, 2, 5, 1, 8, 6, 3] 中尋找 4。

步驟	i	A[i]	比較結果	累計比較次數
1	0	7	7 ≠ 4	1
2	1	2	2 ≠ 4	2
3	2	9	9 ≠ 4	3
4	3	4	命中	4

索引:  0   1   2   3   4
數值: [7] [2] [9] [4] [2]
指針:  ^   →   →   ^(找到)

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

線性檢索(A, target)
設 n = 長度(A)
設 i 由 0至 n-1
    如果 A[i] = target
        傳回 i
傳回 -1

線性檢索(A, target)
設 n = 長度(A)
設 i = 0
當 i < n
    如果 A[i] = target
        傳回 i
    設 i = i + 1
傳回 -1

線性檢索(A, target)
設 n = 長度(A)
如果 n = 0
    傳回 -1
設 i = 0
執行
    如果 A[i] = target
        傳回 i
    設 i = i + 1
當 i < n
傳回 -1

線性檢索(A, target)
設 n = 長度(A)
如果 n = 0
    傳回 -1
設 i = 0
重覆
    如果 A[i] = target
        傳回 i
    設 i = i + 1
直至 i = n
傳回 -1

Check Point：小測／小遊戲（線性檢索）

（請按「下一題」開始）

得分：0 / 0

對分檢索（Binary Search）

重點

只適用於已排序陣列；若資料無序，必須先排序，否則結果不可靠。

Python 小練習：比較「未排序」與「已排序」的對分檢索結果

先直接跑一次，再把 target 改成其他值，觀察未排序時為何會出現錯誤結果。
def binary_search(A, target): low = 0 high = len(A) - 1 while low <= high: mid = (low + high) // 2 if A[mid] == target: return mid elif A[mid] < target: low = mid + 1 else: high = mid - 1 return -1 A_unsorted = [23, 3, 77, 15, 42, 8] A_sorted = sorted(A_unsorted) target = 15 print("未排序 A:", A_unsorted) print("對分檢索找", target, "=>", binary_search(A_unsorted, target)) print("已排序 A:", A_sorted) print("對分檢索找", target, "=>", binary_search(A_sorted, target))
每次比較中間元素，然後把搜尋範圍縮小為一半（排除另一半）。

Python 小練習：印出 low / high / mid（while loop 追蹤）

這段程式會逐步印出指標變化。你可以把 target 改成不存在的值，看看最後如何退出循環。
A = [3, 8, 15, 23, 31, 42, 55, 61, 77, 90] target = 42 low = 0 high = len(A) - 1 step = 0 while low <= high: step += 1 mid = (low + high) // 2 print(f"第 {step} 次：low={low}, high={high}, mid={mid}, A[mid]={A[mid]}") if A[mid] == target: print("✅ 找到！索引 =", mid) break elif A[mid] < target: low = mid + 1 else: high = mid - 1
時間複雜度約為 O(log n)，資料量越大，優勢越明顯。

Python 小練習：估算最壞情況需要幾多步（while loop）

以下模擬「一直向右縮」的最壞情況。嘗試把 n 改成 2048、4096… 觀察步數如何增加。
n = 1024 low = 0 high = n - 1 steps = 0 while low <= high: steps += 1 mid = (low + high) // 2 # 假設 target 永遠比 A[mid] 大，迫使 low 向右縮（模擬最壞情況之一） low = mid + 1 print("n =", n) print("最壞情況步數（估算）=", steps)

定義

對分檢索（binary search）是一種針對已排序陣列的高效率檢索方法。它會重複比較「目前範圍的中間元素」，並根據比較結果決定下一步只保留左半或右半，從而把搜尋範圍快速縮小。

輸入：已排序陣列 A、目標值 target
輸出：目標值的索引，或未找到（常用 -1）

一句概括：每次查看中間位置，然後在較小的一半區間繼續查找。

原理／運作

最常用的寫法會維持兩個邊界：

low：目前範圍的左邊界（起點）
high：目前範圍的右邊界（終點）

每一輪：

計算 mid = (low + high) // 2（取整數，取得中間索引）
比較 A[mid] 與 target

若相等：找到，傳回 mid
如果 A[mid] < target：目標在右半邊 → 令 low = mid + 1
如果 A[mid] > target：目標在左半邊 → 令 high = mid - 1

重點：每次都要排除 mid 本身（±1），否則容易陷入無限迴圈。

例子

陣列：A = [3, 8, 15, 23, 31, 42, 55, 61, 77, 90]，目標：target = 23

low=0, high=5 → mid=2，A[2]=15，15 < 23 → 右半邊
low=3, high=5 → mid=4，A[4]=42，42 > 23 → 左半邊
low=3, high=3 → mid=3，A[3]=23 → 找到，傳回 3

你會看到：元素只有 6 個，但只比較了 3 次便找到。

比較

對分檢索之所以快，是因為每次比較後都能排除一半不可能的範圍。例如 1,000,000 個元素：

線性檢索最壞情況：可能要比較接近 1,000,000 次。
對分檢索最壞情況：約比較 20 次左右（因為 2²⁰ ≈ 1,048,576）。

重點不在精確數字，而在「規模變大時，差距會極端放大」。

常見錯誤

忘記排序：資料未排序就用對分檢索，結果可能找不到已存在的值。
邊界更新錯：把 low = mid 或 high = mid，容易卡住不前進。
重覆元素情況：一般版本只保證「找到其中一個位置」；若題目要求「第一個出現」或「最後一個出現」，需要改寫條件與邊界。

改錯口訣：排序先決條件、mid 計算、low/high 必須縮小。

對分檢索的核心價值在於「把問題規模一分為二」：每一次比較之後，都能確定目標只可能存在於其中一半。但要做到這點，前提是陣列必須已排序，否則你無法確定「目標應該在左還是右」。

從學習角度而言，你應把 low、high、mid 視為三個角色： mid 負責「做判斷」，而 low/high 負責「縮小範圍」。只要你能確保每次迴圈後範圍都縮小，對分檢索就一定會結束。

在實際應用中，對分檢索常常與排序一起出現：先用排序法把資料整理好，之後便可多次使用對分檢索快速查找。因此，理解排序與檢索的關係，是建立「效率思維」的重要一步。

互動示範：對分檢索（可自行生成資料）

對分檢索需要「已排序」資料。系統會自動把生成的資料排序，並用標記顯示 low / mid / high 的變化。

🎮 小遊戲：你就係 Binary Search 程式

圖像化例子：對分檢索的 low / mid / high

目標：在已排序陣列 [1, 3, 4, 6, 8, 9, 11, 15] 中尋找 9。

步驟	low	high	mid	A[mid]	下一步
1	0	7	3	6	目標較大 → low = mid + 1 = 4
2	4	7	5	9	命中

索引:  0   1   2   3   4   5   6   7
數值: [1] [3] [4] [6] [8] [9] [11][15]
              ^mid=3           → low=4
                  low=4   ^mid=5 (找到)

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

對分檢索(A, target)
設 low = 0
設 high = 長度(A) - 1
設 step 由 1至 長度(A)      // 最多做 n 次（實際通常更少）
    如果 low > high
        跳出循環
    設 mid = (low + high) 整除 2
    如果 A[mid] = target
        傳回 mid
    否則如果 A[mid] < target
        設 low = mid + 1
    否則
        設 high = mid - 1
傳回 -1

對分檢索(A, target)
設 low = 0
設 high = 長度(A) - 1
當 low <= high
    設 mid = (low + high) 整除 2
    如果 A[mid] = target
        傳回 mid
    否則如果 A[mid] < target
        設 low = mid + 1
    否則
        設 high = mid - 1
傳回 -1

對分檢索(A, target)
設 low = 0
設 high = 長度(A) - 1
如果 low > high
    傳回 -1
執行
    設 mid = (low + high) 整除 2
    如果 A[mid] = target
        傳回 mid
    否則如果 A[mid] < target
        設 low = mid + 1
    否則
        設 high = mid - 1
當 low <= high
傳回 -1

對分檢索(A, target)
設 low = 0
設 high = 長度(A) - 1
如果 low > high
    傳回 -1
重覆
    設 mid = (low + high) 整除 2
    如果 A[mid] = target
        傳回 mid
    否則如果 A[mid] < target
        設 low = mid + 1
    否則
        設 high = mid - 1
直至 low > high
傳回 -1

Check Point：小測／小遊戲（對分檢索）

（請按「下一題」開始）

得分：0 / 0

增潤其他檢索算法（增潤部份）

增潤部分：點擊展開／收合（雜湊檢索、插值檢索）

以下內容屬增潤部分。建議你先完成「線性檢索」與「對分檢索」，再按需要展開閱讀及挑戰小遊戲。

雜湊檢索（Hash-based Search）﹙增潤部份﹚

重點

雜湊檢索會把「鍵值」透過雜湊函數映射到桶（bucket），平均情況下查找可接近 O(1)。

Python 小練習：用 set 做「是否存在」查找
data = [8, 4, 7, 3, 1, 9, 2, 3, 3] target = 3 # TODO 1：把 data 轉成 set # TODO 2：輸出 target 是否在 set 中（True / False）
碰撞（collision）是雜湊檢索的核心挑戰：不同鍵值可能映射到同一個桶，需要額外策略處理（例如鏈結法、開放定址法）。

Python 小練習：觀察 key % m 造成的碰撞
m = 7 data = [10, 17, 24, 3] # TODO：列印每個數的桶位（key % m） # 提示：10%7、17%7、24%7 會落在同一個桶位
開放定址法（open addressing）其中一種做法是線性探測：桶位已滿就向後逐格查找下一個空位；查找時也要用相同方式探測。

Python 小練習：完成線性探測查找函數（while loop）
def search_linear_probe(table, key): m = len(table) start = key % m t = 0 # TODO：用 while loop 探測最多 m 次 # 規則： # - 遇到 None 代表「未出現過」→ 傳回 False # - 遇到 key → 傳回 True return False T = [None, 10, 17, 24, None, None, 3] print(search_linear_probe(T, 17)) # 預期 True print(search_linear_probe(T, 99)) # 預期 False
與對分檢索相比：雜湊檢索通常不需要先排序，但不擅長「範圍查詢」（例如找出介乎 20 至 40 的所有值）。

Python 小練習：比較「set 查找」與「範圍查找」的差異
data = [5, 18, 23, 39, 40, 41, 100, 101] S = set(data) # TODO 1：用 set 快速判斷 39 是否存在 # TODO 2：用 for loop 找出介乎 20 至 40（含）的所有值（範圍查找）

雜湊檢索（Hash-based Search）是一種利用雜湊函數，把鍵值映射到「位置」或「桶」中，以便快速查找的方式。

常見載體：set / dict（Python）、Hash Table（資料結構）。

選擇雜湊函數 h(key) 把鍵值映射到 0..m-1 的桶位。
若發生碰撞（不同 key 得到相同桶位），就用碰撞處理方法（例如：鏈結法、線性探測）。
查找時用同一個 h(key) 找到「可能位置」，然後根據碰撞處理規則逐步確認。

平均情況可接近 O(1)，但最壞情況（大量碰撞）可能退化。

假設 m = 7，h(key)=key%7：

10%7=3，17%7=3，24%7=3 → 三個值都落在桶位 3（產生碰撞）。
線性探測會把第二個、第三個值放到 4、5（或再往後）的位置。

方法	是否需要排序	典型查找時間	特別擅長
雜湊檢索	不需要	平均 O(1)	大量「是否存在」查找
對分檢索	需要	O(log n)	有序資料、範圍查找更自然

以為雜湊檢索「一定」是 O(1)：若碰撞嚴重或負載因子過高，效能會下降。
自行實作時忘記處理「刪除」：開放定址法通常需要 tombstone，否則查找可能提前停止。
用雜湊表做範圍查找：雜湊表不保序，範圍查找往往要掃描全部資料。

雜湊檢索的核心思想是：不要逐個比對（線性），也不要每次取中位（對分），而是用雜湊函數把「查找」變成「直接定位到某個桶位」。

在程式實務中，Python 的 set 與 dict 已經封裝了雜湊表與碰撞處理，因此通常是最快速、最可靠的做法之一。

不過，在 DSE 或演算法理解層面，仍需要掌握碰撞的原因與處理方法，才能解釋為何雜湊檢索不是「無條件」O(1)。

互動示範：雜湊檢索（100 個數據，10×10 顯示）

你可以生成 100 個數字，系統會以 value mod 10 作為簡化雜湊函數，把資料分到 10 個桶（bucket）。你亦可以自行輸入目標值，觀察「先定位桶」再「在桶內查找」的流程。

🎮 小遊戲：Hash Search（鏈結法 / 線性試探）

圖像化：桶（bucket）與碰撞

以 m=7、h(key)=key%7 為例：

桶位: 0   1   2   3   4   5   6
      [ ] [ ] [ ] [ ] [ ] [ ] [ ]
插入 10 → 10%7=3 → 放入桶 3
插入 17 → 17%7=3 → 桶 3 已滿（碰撞）→ 線性探測：改放桶 4
插入 24 → 24%7=3 → 桶 3/4 已滿 → 改放桶 5

key	h(key)	碰撞？	最終放置
10	3	否	3
17	3	是	4
24	3	是	5

程式示例：不同版本（可切換）

先用「版本 A」理解實務用法，再用「版本 B」理解碰撞處理的底層原理。

做法：建立 m 個桶（陣列），每個桶是一個列表（list）。碰撞時，把多個 key 放在同一桶內。

h(key) = key % m
插入：buckets[h(key)].append(key)
搜尋：先到 buckets[h(target)]，再線性檢查該桶

HashSearch_Chaining(A, target, m)
buckets = array of m empty lists
for each x in A:
    buckets[x % m].append(x)

b = target % m
for each y in buckets[b]:
    if y == target:
        return FOUND
return NOT_FOUND

做法：整個表是一個長度 m 的陣列。碰撞時不開新桶，而是「向後試探」下一個空位。

h(key) = key % m
插入：由 h(key) 起，遇到已佔用就 +1 (mod m) 直到空位
搜尋：同樣由 h(target) 起，逐格試探；遇到空位即可停止（代表找不到）

HashSearch_LinearProbing(A, target, m)
# 假設 A 已經按線性試探方式插入到 table（長度 m）
i = target % m
while table[i] is not EMPTY:
    if table[i] == target:
        return FOUND
    i = (i + 1) % m
return NOT_FOUND

這個版本展示「最常用的實務做法」：用 dict / set 以平均 O(1) 速度查找。

優點：簡潔、可靠；缺點：原理被封裝，需要理解碰撞與負載因子等概念。

雜湊檢索_建立索引(A)
設 H = 空雜湊表
設 i 由 0 至 長度(A) - 1
    如果 H 不包含鍵 A[i] 則
        H[A[i]] = i    // 記錄第一次出現的位置
傳回 H

雜湊檢索(A, target)
設 H = 雜湊檢索_建立索引(A)
如果 H 包含鍵 target 則
    傳回 H[target]
否則
    傳回 -1

雜湊檢索_建立索引(A)
設 H = 空雜湊表
設 i = 0
當 i < 長度(A)
    如果 H 不包含鍵 A[i] 則
        H[A[i]] = i
    i = i + 1
傳回 H

雜湊檢索(A, target)
設 H = 雜湊檢索_建立索引(A)
如果 H 包含鍵 target 則
    傳回 H[target]
否則
    傳回 -1

雜湊檢索_建立索引(A)
設 H = 空雜湊表
設 i = 0
執行
    如果 H 不包含鍵 A[i] 則
        H[A[i]] = i
    i = i + 1
當 i < 長度(A)
傳回 H

雜湊檢索(A, target)
設 H = 雜湊檢索_建立索引(A)
如果 H 包含鍵 target 則
    傳回 H[target]
否則
    傳回 -1

雜湊檢索_建立索引(A)
設 H = 空雜湊表
設 i = 0
重覆
    如果 H 不包含鍵 A[i] 則
        H[A[i]] = i
    i = i + 1
直至 i == 長度(A)
傳回 H

雜湊檢索(A, target)
設 H = 雜湊檢索_建立索引(A)
如果 H 包含鍵 target 則
    傳回 H[target]
否則
    傳回 -1

這個版本用簡化版雜湊表說明「碰撞處理」：若桶位已被佔用，就向後逐格探測（linear probing）。

注意：真實系統還要處理刪除標記（tombstone）與再雜湊（rehash）。

插入_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t 由 0 至 m - 1
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        T[idx] = key
        傳回 True
傳回 False

搜尋_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t 由 0 至 m - 1
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        傳回 False
    如果 T[idx] == key 則
        傳回 True
傳回 False

插入_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
當 t < m
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        T[idx] = key
        傳回 True
    t = t + 1
傳回 False

搜尋_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
當 t < m
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        傳回 False
    如果 T[idx] == key 則
        傳回 True
    t = t + 1
傳回 False

插入_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
執行
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        T[idx] = key
        傳回 True
    t = t + 1
當 t < m
傳回 False

搜尋_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
執行
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        傳回 False
    如果 T[idx] == key 則
        傳回 True
    t = t + 1
當 t < m
傳回 False

插入_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
重覆
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        T[idx] = key
        傳回 True
    t = t + 1
直至 t == m
傳回 False

搜尋_線性探測(T, key)
設 m = 長度(T)
設 start = key mod m
設 t = 0
重覆
    設 idx = (start + t) mod m
    如果 T[idx] 為 空 則
        傳回 False
    如果 T[idx] == key 則
        傳回 True
    t = t + 1
直至 t == m
傳回 False

Check Point：雜湊檢索

（載入中…）

插值檢索（Interpolation Search）﹙增潤部份﹚

重點

插值檢索要求資料 已排序，並假設數值分佈相對均勻，才有機會比對分檢索更快。

Python 小練習：建立已排序資料並測試查找
a = sorted([15, 1, 9, 3, 11, 6, 8, 4]) target = 9 print(a) # TODO：先用「in」測試 target 是否存在（作為對照） print(target in a)
核心公式（估算位置）： pos = low + (target - A[low]) * (high - low) / (A[high] - A[low])

Python 小練習：只計算一次 pos（觀察估算位置）
a = [1, 3, 4, 6, 8, 9, 11, 15] low = 0 high = len(a) - 1 target = 9 # TODO：用公式計算 pos（用整數除法 //） pos = low + (target - a[low]) * (high - low) // (a[high] - a[low]) print("pos =", pos, "a[pos] =", a[pos])
插值檢索最壞情況仍可能退化到 O(n)，常見原因包括：分佈極不均勻、或資料大量重複導致估算失真。

Python 小練習：加入防護避免除以零
a = [5, 5, 5, 5, 5] # a[low] == a[high] target = 5 # TODO：當 a[low] == a[high] 時，避免用 (a[high]-a[low]) 做除法 # 提示：如果 a[low] == target，直接傳回 low；否則傳回 -1

插值檢索（Interpolation Search）是一種在已排序資料中，利用數值大小比例估算目標位置的檢索方法。

它可視為「會估算位置的對分檢索」，不一定每次都取正中間。

維持 low 與 high（目標可能存在的邊界）。
用比例公式估算 pos（更接近 target 的位置）。
比較 A[pos] 與 target，然後更新 low/high。

若分佈均勻，平均複雜度可達到 O(log log n)（理想情況）；但最壞仍可能是 O(n)。

陣列：[1, 3, 4, 6, 8, 9, 11, 15]，target=9

因為 9 靠近右側，所以估算的 pos 也會較靠右（不一定是中位 3 或 4）。

方法	需要排序	位置選擇	平均情況
對分檢索	需要	永遠取中位	O(log n)
插值檢索	需要	按比例估算 pos	分佈均勻時更快

忘記檢查 A[low]==A[high]：會造成除以零。
沒有檢查 target 是否在 [A[low], A[high]]：pos 可能越界。
把插值檢索當成「一定比對分快」：若分佈不均勻，可能退化並變慢。

插值檢索的直覺是：如果資料值分佈均勻，目標值 90 應該比目標值 10 更接近右邊，因此可以先猜一個「更靠近目標的中間點」來比較。

對分檢索每次都取正中間，保證把搜尋範圍對半縮小；插值檢索改用比例估算位置，可能更快，也可能因估算不準而退化。

互動示範：插值檢索（100 個數據，10×10 顯示）

插值檢索會利用 target 在數值範圍中的相對位置去估算 pos。系統會自動把資料排序，並標示 low / pos / high 的移動。

🎮 小遊戲：你就係 Interpolation Search 程式

圖像化：pos 估算位置

pos = low + (target - A[low]) * (high - low) / (A[high] - A[low])

A: [1, 3, 4, 6, 8, 9, 11, 15]
    low ------------------- high
                 ^ pos（估算靠近 target）

當資料分佈均勻，pos 的估算通常更接近目標；當分佈不均或重複值多，pos 可能失真。

程式示例：不同版本（可切換）

建議先閱讀版本 A，再閱讀版本 B 的防護條件。

利用比例估算位置 pos，在資料分佈較均勻時可快於對分檢索。

此版本假設 A[low] != A[high]，並省略部分防護。

插值檢索(A, target)
設 low = 0
設 high = 長度(A) - 1

設 t 由 1 至 長度(A)
    如果 low > high 則
        傳回 -1
    如果 target < A[low] 或 target > A[high] 則
        傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1

傳回 -1

插值檢索(A, target)
設 low = 0
設 high = 長度(A) - 1

當 low <= high 且 target >= A[low] 且 target <= A[high]
    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1

傳回 -1

插值檢索(A, target)
設 low = 0
設 high = 長度(A) - 1

執行
    如果 low > high 或 target < A[low] 或 target > A[high] 則
        傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1
當 low <= high

傳回 -1

插值檢索(A, target)
設 low = 0
設 high = 長度(A) - 1

重覆
    如果 low > high 或 target < A[low] 或 target > A[high] 則
        傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1
直至 low > high

傳回 -1

加入防護：當 A[low]==A[high] 時避免除以零；並把 pos 夾在 [low, high] 之內。

插值檢索_防護版(A, target)
設 low = 0
設 high = 長度(A) - 1

設 t 由 1 至 長度(A)
    如果 low > high 或 target < A[low] 或 target > A[high] 則
        傳回 -1

    如果 A[low] == A[high] 則
        如果 A[low] == target 則 傳回 low
        否則 傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 pos < low 則 pos = low
    如果 pos > high 則 pos = high

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1

傳回 -1

插值檢索_防護版(A, target)
設 low = 0
設 high = 長度(A) - 1

當 low <= high 且 target >= A[low] 且 target <= A[high]
    如果 A[low] == A[high] 則
        如果 A[low] == target 則 傳回 low
        否則 傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 pos < low 則 pos = low
    如果 pos > high 則 pos = high

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1

傳回 -1

插值檢索_防護版(A, target)
設 low = 0
設 high = 長度(A) - 1

執行
    如果 low > high 或 target < A[low] 或 target > A[high] 則
        傳回 -1

    如果 A[low] == A[high] 則
        如果 A[low] == target 則 傳回 low
        否則 傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 pos < low 則 pos = low
    如果 pos > high 則 pos = high

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1
當 low <= high

傳回 -1

插值檢索_防護版(A, target)
設 low = 0
設 high = 長度(A) - 1

重覆
    如果 low > high 或 target < A[low] 或 target > A[high] 則
        傳回 -1

    如果 A[low] == A[high] 則
        如果 A[low] == target 則 傳回 low
        否則 傳回 -1

    設 pos = low + (target - A[low]) * (high - low) div (A[high] - A[low])

    如果 pos < low 則 pos = low
    如果 pos > high 則 pos = high

    如果 A[pos] == target 則
        傳回 pos
    如果 A[pos] < target 則
        low = pos + 1
    否則
        high = pos - 1
直至 low > high

傳回 -1

Check Point：插值檢索

（載入中…）

甚麼是排序？

重點

「排序」的核心任務：把資料按指定規則重新排列，例如由小至大或由大至小。
排序後，很多事情會變得更容易：例如更快檢索（對分檢索）、更容易找最大/最小、以及更清晰的輸出。
不同排序法的差異主要在於：時間複雜度、是否需要額外記憶體、以及是否穩定排序。
本課程的核心排序法：選擇排序法、插入排序法、冒泡排序法；合併排序法與快速排序法只需認識其存在與基本原理；其餘會以增潤形式介紹（已清楚標示）。

定義

排序是把資料集合（例如陣列）依照某個比較規則重新排列。最常見的規則是「由小至大」，也可以是「由大至小」，或自訂規則（例如先按分數、再按姓名）。

排序後常見效果：

最小值在最前，最大值在最後（由小至大時）。
同類資料集中，便於做統計與後續處理。
為某些檢索算法（如對分檢索）提供必要前提。

原理／運作

你可以把排序理解成「不斷把元素移到合適位置」的過程，但不同排序法搬運的策略不同：

選擇排序法：每輪在未排序區找最小值，放到前面。
插入排序法：像整理撲克牌一樣，把新牌插入到已排序區的合適位置。
冒泡排序法：相鄰比較、必要時交換，較大的元素逐步「冒」到尾端。
合併排序法（只需認識）：分開→排序→合併，透過合併把兩個已排序列表整合。
快速排序法（只需認識）：選 pivot，把資料分割成兩邊，再遞歸排序。
計數排序法／基數排序法（增潤）：利用「值域」或「位數」的特性，避免大量比較。

排序的本質不是背公式，而是理解「每一輪在做甚麼」以及「為甚麼能逐步接近正確次序」。

例子

假設你要在 100 個數字中找目標值：如果資料未排序，你往往只能用線性檢索；如果先排序，就能使用對分檢索，查找步數大幅下降。

因此，很多題目其實是「先排序」再「檢索」的組合思維。

比較

層級	排序法	要求
課程內（必須掌握流程）	選擇排序法、插入排序法、冒泡排序法	能寫出偽代碼／追蹤表，理解比較與交換如何發生
只需認識（知道存在與原理）	合併排序法、快速排序法	知道核心想法（分割／合併、pivot 分割），不用深入寫完整實作
增潤（拓闊視野）	計數排序法、基數排序法	理解它們為何在某些條件下很快，以及限制是甚麼

常見錯誤

只背名字：說得出「冒泡排序法」，卻說不出每一輪在做甚麼。
忽略比較方向：由小至大與由大至小的交換條件相反。
忽略限制：計數排序法／基數排序法快，但只適合特定資料型態（例如整數、位數固定）。

改正方法：每學一種排序法，都要能用一句話說出「它每一輪的目標」是甚麼。

排序不只是「把數字排好看一點」，而是一種非常常用的前置處理。很多看似不同的問題（例如找最大值、找第 k 大、快速查找某個值）在排序後都會變得容易。

在學習排序法時，你可以把陣列想像成一排卡牌。不同排序法的差異，就是「你每次用甚麼策略把卡牌搬到合適的位置」：有的會不斷把最小值搬到前面，有的會把新牌插入到已排好的位置，也有的會用 pivot 把牌分成兩邊再處理。

另外，排序題目常見的得分位在於「追蹤過程」：你能否清楚指出每一步比較了哪兩個元素、是否交換，陣列如何改變。本頁面的互動示範會用標記顯示當前比較的位置，幫你建立正確的追蹤習慣。

選擇排序法（Selection Sort）

重點

每一輪在「未排序區」中找出最小值，放到「已排序區」的尾端。

Python 小練習：做第 1 輪（找最小值並交換）

先只做 i = 0 這一輪。然後把 i 改成 1，再做下一輪。
A = [29, 10, 14, 37, 13] i = 0 # 第 0 輪：把最小值放到索引 0 min_index = i for j in range(i + 1, len(A)): if A[j] < A[min_index]: min_index = j print("未交換前：", A) print("本輪找到最小值：", A[min_index], "在索引", min_index) # 交換（把最小值放到 A[i]） A[i], A[min_index] = A[min_index], A[i] print("交換後：", A)
時間複雜度一般為 O(n²)；即使資料已接近排序，仍然要做大量比較。

Python 小練習：計算比較次數（for loop）

選擇排序法的比較次數與資料內容無關，只與 n 有關。試試改 n。
def selection_comparisons(n): count = 0 for i in range(n - 1): for j in range(i + 1, n): count += 1 return count for n in [5, 10, 20]: print("n =", n, "比較次數 =", selection_comparisons(n))
一般情況下屬於不穩定排序：相同鍵值的元素，排序後相對次序可能改變。

Python 小練習：用「標籤」觀察不穩定

留意：(2, "A") 與 (2, "B") 的相對次序會在交換後改變。
A = [(2, "A"), (2, "B"), (1, "C")] def selection_sort_pairs(A): A = A[:] # 複製，避免改到原本 n = len(A) for i in range(n - 1): min_index = i for j in range(i + 1, n): if A[j][0] < A[min_index][0]: min_index = j A[i], A[min_index] = A[min_index], A[i] # 交換可能打亂相同鍵值的次序 return A print("Before:", A) print("After :", selection_sort_pairs(A))

選擇排序法的思路很像「選拔」：把最小值找出來，放到第一位；再把剩下的最小值找出來，放到第二位。由於流程固定、變數少，它特別適合用來練習「找最小值」與「交換」這兩個常見技巧。

不過，你要留意它的效率限制：即使資料本身已經差不多排序好，選擇排序法仍然會照樣把每一輪的搜尋做完。這意味著它的比較次數通常仍接近 n²，在資料量大時會明顯變慢。

學習選擇排序法時，建議你同時建立「已排序／未排序」的視覺：左邊區域每輪增加一格，右邊區域逐步縮小。只要能清楚說出「第 i 輪後，前 i 個元素已經在正確位置」，你就真正理解了它的結構。

互動示範：選擇排序法（可自行生成資料）

觀察每一輪如何在「未排序區」找出最小值，並交換到前面。系統會標記「目前比較」與「目前最小值」的位置。

🎮 小遊戲：扮演選擇排序法（簡易版 / 空運行版）

圖像化例子：選擇排序法（每一輪選最小）

示例陣列：[5, 1, 4, 2]

輪次 i	未排序範圍	找到的最小值	交換後結果
0	[5, 1, 4, 2]	1	[1, 5, 4, 2]
1	[5, 4, 2]	2	[1, 2, 4, 5]
2	[4, 5]	4	[1, 2, 4, 5]

提示：即使陣列幾乎已排序，選擇排序法仍會完整掃描未排序範圍來找最小值。

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

選擇排序法(A)
設 n = 長度(A)
設 i 由 0至 n-2
    設 minIndex = i
    設 j 由 i+1至 n-1
        如果 A[j] < A[minIndex]
            設 minIndex = j
    如果 minIndex ≠ i
        設 temp = A[i]
        設 A[i] = A[minIndex]
        設 A[minIndex] = temp

選擇排序法(A)
設 n = 長度(A)
設 i = 0
當 i <= n-2
    設 minIndex = i
    設 j = i + 1
    當 j <= n-1
        如果 A[j] < A[minIndex]
            設 minIndex = j
        設 j = j + 1
    如果 minIndex ≠ i
        設 temp = A[i]
        設 A[i] = A[minIndex]
        設 A[minIndex] = temp
    設 i = i + 1

選擇排序法(A)
設 n = 長度(A)
如果 n <= 1
    傳回
設 i = 0
執行
    設 minIndex = i
    設 j = i + 1
    當 j <= n-1
        如果 A[j] < A[minIndex]
            設 minIndex = j
        設 j = j + 1
    如果 minIndex ≠ i
        設 temp = A[i]
        設 A[i] = A[minIndex]
        設 A[minIndex] = temp
    設 i = i + 1
當 i <= n-2

選擇排序法(A)
設 n = 長度(A)
如果 n <= 1
    傳回
設 i = 0
重覆
    設 minIndex = i
    設 j = i + 1
    當 j <= n-1
        如果 A[j] < A[minIndex]
            設 minIndex = j
        設 j = j + 1
    如果 minIndex ≠ i
        設 temp = A[i]
        設 A[i] = A[minIndex]
        設 A[minIndex] = temp
    設 i = i + 1
直至 i > n-2

Check Point：小測／小遊戲（選擇排序法）

（請按「下一題」開始）

得分：0 / 0

插入排序法（Insertion Sort）

重點

維持「左邊已排序、右邊未排序」：每次把一個元素插入到已排序區的正確位置。

Python 小練習：把 key 插入已排序區（while loop）

這段程式示範「搬移」與「插入」的核心動作，是理解插入排序法的關鍵。
A = [10, 14, 29, 37, 13] # 假設前 4 個已排序，最後一個是 key key = A[4] j = 3 print("開始：", A, "key =", key) while j >= 0 and A[j] > key: A[j + 1] = A[j] # 向右搬移 j -= 1 A[j + 1] = key print("插入後：", A)
對「幾乎已排序」的資料特別有效；搬移次數很少，速度可以很快。

Python 小練習：比較「幾乎已排序」與「完全倒序」的搬移次數

把陣列改一改，再觀察 shifts（搬移次數）如何大幅改變。
def insertion_sort_count_shifts(A): A = A[:] shifts = 0 for i in range(1, len(A)): key = A[i] j = i - 1 while j >= 0 and A[j] > key: A[j + 1] = A[j] shifts += 1 j -= 1 A[j + 1] = key return shifts, A almost = [1, 2, 3, 5, 4, 6, 7, 8] reversed_list = [8, 7, 6, 5, 4, 3, 2, 1] print("幾乎已排序 shifts =", insertion_sort_count_shifts(almost)[0]) print("完全倒序 shifts =", insertion_sort_count_shifts(reversed_list)[0])
最佳情況約為 O(n)（已排序），最壞情況約為 O(n²)（倒序）。

Python 小練習：同一個 n，最佳與最壞搬移次數差幾多？

下面用相同 n 比較「已排序」與「倒序」的搬移次數。
def insertion_sort_count_shifts(A): A = A[:] shifts = 0 for i in range(1, len(A)): key = A[i] j = i - 1 while j >= 0 and A[j] > key: A[j + 1] = A[j] shifts += 1 j -= 1 A[j + 1] = key return shifts for n in [10, 20]: sorted_list = list(range(1, n + 1)) reversed_list = list(range(n, 0, -1)) best = insertion_sort_count_shifts(sorted_list) worst = insertion_sort_count_shifts(reversed_list) print("n =", n, "| 已排序 shifts =", best, "| 倒序 shifts =", worst)

插入排序法的特點在於它不急於把整個陣列一次過整理好，而是把「已排序」部分逐步擴大。每次你只處理一個新元素，把它放回正確位置，便令左邊區域再次保持有序。

它的效率很依賴資料狀態：若資料完全倒序，每次插入都要把整段已排序部分向右搬，會造成大量搬移與比較，速度就會變慢；但若資料本來就差不多排好，大部分元素只需搬移一兩格，便能迅速完成。

因此，在面對「資料常常只做小幅更新」的情境（例如新增一個分數到已排序名單），插入排序法的思路非常實用：你不用重新排序整份名單，只要把新元素插入到正確位置即可。

互動示範：插入排序法（可自行生成資料）

觀察 key 如何從右邊取出，並向左插入到「已排序區」的正確位置；被移動的元素會被標記。

🎮 小遊戲：扮演插入排序法（每輪拖 key 一次）

圖像化例子：插入排序法（把 key 插入左邊的已排序區）

示例陣列：[5, 1, 4, 2]

i	key	左邊已排序區	插入後結果
1	1	[5]	[1, 5, 4, 2]
2	4	[1, 5]	[1, 4, 5, 2]
3	2	[1, 4, 5]	[1, 2, 4, 5]

提示：若原本已接近排序，插入排序法的移動次數會明顯減少。

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

插入排序法(A)
設 n = 長度(A)
設 i 由 1至 n-1
    設 key = A[i]
    設 j = i - 1
    當 j >= 0 並且 A[j] > key
        設 A[j+1] = A[j]
        設 j = j - 1
    設 A[j+1] = key

插入排序法(A)
設 n = 長度(A)
設 i = 1
當 i <= n-1
    設 key = A[i]
    設 j = i - 1
    當 j >= 0 並且 A[j] > key
        設 A[j+1] = A[j]
        設 j = j - 1
    設 A[j+1] = key
    設 i = i + 1

插入排序法(A)
設 n = 長度(A)
如果 n <= 1
    傳回
設 i = 1
執行
    設 key = A[i]
    設 j = i - 1
    當 j >= 0 並且 A[j] > key
        設 A[j+1] = A[j]
        設 j = j - 1
    設 A[j+1] = key
    設 i = i + 1
當 i <= n-1

插入排序法(A)
設 n = 長度(A)
如果 n <= 1
    傳回
設 i = 1
重覆
    設 key = A[i]
    設 j = i - 1
    當 j >= 0 並且 A[j] > key
        設 A[j+1] = A[j]
        設 j = j - 1
    設 A[j+1] = key
    設 i = i + 1
直至 i > n-1

Check Point：小測／小遊戲（插入排序法）

（請按「下一題」開始）

得分：0 / 0

冒泡排序法（Bubble Sort）

重點

反覆比較相鄰元素並在需要時交換；每一輪會把一個「最大值」推到尾端。

Python 小練習：做第 1 輪（觀察最大值如何被推到尾端）

留意每一步的陣列變化：較大的值會一步一步「冒」到右邊。
A = [5, 1, 4, 2, 8] print("開始：", A) for i in range(len(A) - 1): if A[i] > A[i + 1]: A[i], A[i + 1] = A[i + 1], A[i] print(f"i={i} 後：", A) print("第 1 輪後最大值應在尾端：", A[-1])
多輪重複以上過程，直到整個陣列已排序；時間複雜度一般為 O(n²)。

Python 小練習：每一輪後印出陣列（for loop）

這能「圖像化」冒泡排序法的過程：越大的值越早固定在右邊。
def bubble_sort_show(A): A = A[:] n = len(A) for p in range(n - 1): for i in range(n - 1 - p): if A[i] > A[i + 1]: A[i], A[i + 1] = A[i + 1], A[i] print(f"第 {p + 1} 輪後：", A) return A bubble_sort_show([5, 1, 4, 2, 8])
可加入「早停」：若某一輪沒有交換，代表已排序完成，可提前停止。

Python 小練習：比較「早停」能節省幾多輪

已排序的陣列用早停會非常快；試試把輸入改成「幾乎已排序」。
def bubble_sort_early_stop(A): A = A[:] n = len(A) passes = 0 for p in range(n - 1): swapped = False for i in range(n - 1 - p): if A[i] > A[i + 1]: A[i], A[i + 1] = A[i + 1], A[i] swapped = True passes += 1 if not swapped: break return passes, A print("已排序資料：需要", bubble_sort_early_stop([1, 2, 3, 4, 5])[0], "輪") print("亂序資料：需要", bubble_sort_early_stop([5, 1, 4, 2, 8])[0], "輪")

冒泡排序法可以看成「不斷把錯位的相鄰元素調回正確次序」。它最大的教學價值，是令你看見排序的本質：排序其實就是透過比較，逐步消除「逆序」的情況。

當你理解了「每一輪會把最大值放到最右」這件事，你便能自然推導出內迴圈的範圍為何可以逐步縮短，以及為何早停優化在「已接近排序」的資料中會特別有效。

不過，冒泡排序法的效率限制同樣值得記住：當資料量很大時，兩層迴圈會帶來大量比較與交換。因此，在需要處理大量資料時，冒泡排序法通常只適合作為概念示範，而不是首選方法。

互動示範：冒泡排序法（可自行生成資料）

觀察相鄰比較與交換：較大的元素會逐步「冒」到右端。系統會標記正在比較的一對元素。

🎮 小遊戲：Bubble Sort（比較相鄰一對）

圖像化例子：冒泡排序法（把最大值「冒」到右端）

示例陣列：[5, 1, 4, 2]

輪次	相鄰比較與交換	輪次結束後
第 1 輪	(5,1)→換；(5,4)→換；(5,2)→換	[1, 4, 2, 5]
第 2 輪	(1,4)→不換；(4,2)→換	[1, 2, 4, 5]

加入「若某一輪沒有交換就提前停止」的優化，可令近乎排序的情況更快。

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

冒泡排序法(A)
設 n = 長度(A)
設 pass 由 0至 n-2
    設 i 由 0至 n-2-pass
        如果 A[i] > A[i+1]
            設 temp = A[i]
            設 A[i] = A[i+1]
            設 A[i+1] = temp

冒泡排序法(A)
設 n = 長度(A)
設 pass = 0
當 pass <= n-2
    設 i = 0
    當 i <= n-2-pass
        如果 A[i] > A[i+1]
            設 temp = A[i]
            設 A[i] = A[i+1]
            設 A[i+1] = temp
        設 i = i + 1
    設 pass = pass + 1

冒泡排序法(A)    // 示範 do while：用 swapped 早停
設 n = 長度(A)
設 pass = 0
執行
    設 swapped = false
    設 i = 0
    當 i <= n-2-pass
        如果 A[i] > A[i+1]
            設 temp = A[i]
            設 A[i] = A[i+1]
            設 A[i+1] = temp
            設 swapped = true
        設 i = i + 1
    設 pass = pass + 1
當 swapped = true 並且 pass <= n-2

冒泡排序法(A)    // 示範 repeat until：用 swapped 早停
設 n = 長度(A)
設 pass = 0
重覆
    設 swapped = false
    設 i = 0
    當 i <= n-2-pass
        如果 A[i] > A[i+1]
            設 temp = A[i]
            設 A[i] = A[i+1]
            設 A[i+1] = temp
            設 swapped = true
        設 i = i + 1
    設 pass = pass + 1
直至 swapped = false 或 pass > n-2

Check Point：小測／小遊戲（冒泡排序法）

（請按「下一題」開始）

得分：0 / 0

合併兩個已排序的列表（Merge Two Sorted Lists）

重點

使用兩個指針 i、j，分別指向兩個列表當前尚未合併的元素。

Python 小練習：手動追蹤 i / j 的移動
A = [1, 4, 7, 8] B = [2, 3, 9] # TODO：用 print 方式逐步印出 i、j、以及目前選了哪個值放入 output # 提示：先建立 i=0, j=0, output=[]
每次比較 A[i] 與 B[j]，把較小者放入輸出，然後移動相應指針（穩定性：相等時優先取左邊可保持穩定）。

Python 小練習：相等時先取 A（維持穩定）
A = [1, 2, 2, 5] B = [2, 2, 4] # TODO：完成合併，並確保相等時先取 A 的 2 # 觀察輸出中 2 的先後順序
時間複雜度為 O(n+m)，因為每個元素最多被放入輸出一次；這正是合併排序法能達到 O(n log n) 的關鍵子步驟。

Python 小練習：確認合併次數
import random A = sorted(random.sample(range(0, 50), 8)) B = sorted(random.sample(range(0, 50), 6)) print("A =", A) print("B =", B) # TODO：合併後輸出長度是否為 len(A)+len(B) # TODO：用一個計數器記錄你做了多少次「放入 output」

合併兩個已排序列表是指把兩個已按遞增（或遞減）順序排列的列表，合併成一個同樣保持排序的列表。

它是合併排序法（Merge Sort）的核心子步驟。

設兩個指針 i、j 指向兩個列表的起點。
比較 A[i] 與 B[j]，把較小者放入輸出，並移動該指針。
當其中一個列表用盡，把另一個列表剩餘部分直接接到輸出尾端。

A=[1,4,7,8]、B=[2,3,9]

輸出：[1,2,3,4,7,8,9]

做法	時間複雜度	特點
雙指針合併	O(n+m)	一次線性掃描即可完成
把兩個列表合併後再排序	視乎排序法	通常更慢，且浪費「已排序」的資訊

忘記把「剩餘的一邊」接回輸出，導致遺漏元素。
相等時處理不一致：若要穩定，通常相等時先取左邊（A）。
在未排序的列表上直接使用本方法：前提是兩個列表已排序。

合併排序法（Merge Sort）之所以高效，是因為它把問題分成兩半後，最後用「線性時間」把兩個已排序子列表合併起來。

因此，在學合併排序法之前，必須先熟悉這個合併子程序：雙指針、逐步比較、把較小者放入輸出。

互動示範：合併兩個已排序列表

系統會生成兩個已排序的列表（A 與 B），並用指針 i、j 逐步合併到新列表。你可以調整每個列表的長度與數值範圍，然後按「下一步」觀察指針如何前進。

🎮 小遊戲：Merge Two Sorted Lists

圖像化：i / j 指針的移動

A = [1, 4, 7, 8]
     i^
B = [2, 3, 9]
     j^

比較 A[i]=1 與 B[j]=2 → 取 1，i++
再比較 A[i]=4 與 B[j]=2 → 取 2，j++
...

程式示例：偽代碼與 Python（可切換）

此合併子程序會在合併排序法中反覆使用。

合併兩個已排序列表(A, B)
設 i = 0
設 j = 0
設 output = 空列表

設 k 由 1 至 長度(A) + 長度(B)
    如果 i == 長度(A) 則
        將 B[j] 加入 output
        j = j + 1
    否則 如果 j == 長度(B) 則
        將 A[i] 加入 output
        i = i + 1
    否則 如果 A[i] <= B[j] 則
        將 A[i] 加入 output
        i = i + 1
    否則
        將 B[j] 加入 output
        j = j + 1

傳回 output

合併兩個已排序列表(A, B)
設 i = 0
設 j = 0
設 output = 空列表

當 i < 長度(A) 且 j < 長度(B)
    如果 A[i] <= B[j] 則
        將 A[i] 加入 output
        i = i + 1
    否則
        將 B[j] 加入 output
        j = j + 1

當 i < 長度(A)
    將 A[i] 加入 output
    i = i + 1

當 j < 長度(B)
    將 B[j] 加入 output
    j = j + 1

傳回 output

合併兩個已排序列表(A, B)
設 i = 0
設 j = 0
設 output = 空列表

如果 長度(A) == 0 則 傳回 B
如果 長度(B) == 0 則 傳回 A

執行
    如果 i == 長度(A) 或 j == 長度(B) 則
        跳出
    如果 A[i] <= B[j] 則
        將 A[i] 加入 output
        i = i + 1
    否則
        將 B[j] 加入 output
        j = j + 1
當 True

當 i < 長度(A)
    將 A[i] 加入 output
    i = i + 1
當 j < 長度(B)
    將 B[j] 加入 output
    j = j + 1

傳回 output

合併兩個已排序列表(A, B)
設 i = 0
設 j = 0
設 output = 空列表

重覆
    如果 i == 長度(A) 或 j == 長度(B) 則
        跳出
    如果 A[i] <= B[j] 則
        將 A[i] 加入 output
        i = i + 1
    否則
        將 B[j] 加入 output
        j = j + 1
直至 False

當 i < 長度(A)
    將 A[i] 加入 output
    i = i + 1
當 j < 長度(B)
    將 B[j] 加入 output
    j = j + 1

傳回 output

Check Point：合併兩個已排序列表

（載入中…）

增潤其他排序算法（增潤部份）

增潤部分：點擊展開／收合（合併排序法、快速排序法、計數排序法、基數排序法）

以下內容屬增潤部分。建議你先完成「選擇排序法／插入排序法／冒泡排序法」等核心排序法，再按需要展開閱讀及挑戰小遊戲。

合併排序法（Merge Sort）﹙增潤部份﹚

重點

採用「分治」：先把陣列分成兩半，分到最細，再把兩個已排序子陣列合併。

Python 小練習：實作 merge（用 while loop 合併兩個已排序 list）

合併是合併排序法的核心。請先確定 merge() 能正確合併，再延伸到完整排序。
def merge(left, right): i = 0 j = 0 out = [] while i < len(left) and j < len(right): if left[i] <= right[j]: out.append(left[i]) i += 1 else: out.append(right[j]) j += 1 out.extend(left[i:]) out.extend(right[j:]) return out print(merge([1, 3, 5], [2, 4, 6]))
時間複雜度一般為 O(n log n)，表現穩定；資料是否接近排序影響不大。

Python 小練習：計算分割層數（大約等於 log₂(n)）

每一層把資料量減半，直到每份只剩 1 個元素。
n = 16 level = 0 size = n while size > 1: size = size // 2 level += 1 print("n =", n) print("分割到每份 1 個元素，需要層數 =", level)
通常需要額外 O(n) 記憶體（合併時建立新陣列），換取穩定且可預期的效率。

Python 小練習：觀察「傳回新 list」與「原 list 不變」

合併排序法常以「傳回新陣列」方式實作，因此會用到額外空間。
def merge(left, right): i = 0 j = 0 out = [] while i < len(left) and j < len(right): if left[i] <= right[j]: out.append(left[i]) i += 1 else: out.append(right[j]) j += 1 out.extend(left[i:]) out.extend(right[j:]) return out def merge_sort(A): if len(A) <= 1: return A[:] # 傳回新 list mid = len(A) // 2 left = merge_sort(A[:mid]) right = merge_sort(A[mid:]) return merge(left, right) A = [29, 10, 14, 37, 13] B = merge_sort(A) print("原本 A:", A) print("新結果 B:", B) print("A 與 B 是否同一個物件？", A is B)

合併排序法是你正式接觸「分而治之」思維的重要起點：先把大問題拆小，解決小問題後再把答案合併成完整解。你不必一開始就能背出所有細節，但你必須能說清楚「拆分」與「合併」各自的目的。

對很多學生而言，最難的是遞歸：你會覺得程式好像在「自己叫自己」。其實你只需要牢記兩點：第一，必須有停止條件；第二，每一次遞歸都令問題變小（例如陣列長度減半）。只要這兩點成立，遞歸就會自然收斂並返回答案。

合併排序法的另一個關鍵是「合併」本身非常規律：兩個已排序列表，就像兩條已排好隊的隊伍，你只要每次選出較小的一個向前走，最終就能合成一條更長的已排序隊伍。這種合併過程是線性的，因此整體時間複雜度可以保持在 O(n log n)。

互動示範：合併排序法（100 個數據，10×10 顯示）

合併排序法的示範預設使用 100 個數據（10×10 排列）。你可以改變數量與範圍，並選擇排序方向（由小至大／由大至小）。

🎮 小遊戲：Merge Sort（先一半一半分割，再合併）

圖像化例子：合併排序法的「分」與「合」

示例陣列：[8, 4, 7, 3, 1, 9, 2]

分（Divide）：
[8, 4, 7, 3, 1, 9, 2]
→ [8, 4, 7, 3] + [1, 9, 2]
→ [8, 4] + [7, 3] + [1, 9] + [2]
→ [8] [4] [7] [3] [1] [9] [2]

合（Conquer / Merge）：
[8] + [4] → [4, 8]
[7] + [3] → [3, 7]
[4, 8] + [3, 7] → [3, 4, 7, 8]
[1] + [9] → [1, 9]
[1, 9] + [2] → [1, 2, 9]
[3, 4, 7, 8] + [1, 2, 9] → [1, 2, 3, 4, 7, 8, 9]

關鍵：每一次「合併」都在合併兩個已排序的列表；因此上一節已先獨立講解「合併兩個已排序列表」。

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

提示：可在 Python 分頁按「Run」觀察輸出；偽代碼分頁用於對照 DSE 風格。

合併排序法(A)
如果 長度(A) <= 1
    傳回 A
設 mid = 長度(A) 整除 2
設 left = 合併排序法(A[0..mid-1])
設 right = 合併排序法(A[mid..最後])
傳回 合併_for(left, right)

合併_for(left, right)    // 示範 for loop
設 i = 0
設 j = 0
設 out = 空陣列
設 k 由 1至 長度(left)+長度(right)
    如果 i = 長度(left)
        加入 right[j] 到 out
        設 j = j + 1
    否則如果 j = 長度(right)
        加入 left[i] 到 out
        設 i = i + 1
    否則如果 left[i] <= right[j]
        加入 left[i] 到 out
        設 i = i + 1
    否則
        加入 right[j] 到 out
        設 j = j + 1
傳回 out

合併排序法(A)
如果 長度(A) <= 1
    傳回 A
設 mid = 長度(A) 整除 2
設 left = 合併排序法(A[0..mid-1])
設 right = 合併排序法(A[mid..最後])
傳回 合併_while(left, right)

合併_while(left, right)  // 示範 while loop
設 i = 0
設 j = 0
設 out = 空陣列
當 i < 長度(left) 並且 j < 長度(right)
    如果 left[i] <= right[j]
        加入 left[i] 到 out；設 i = i + 1
    否則
        加入 right[j] 到 out；設 j = j + 1
當 i < 長度(left)
    加入 left[i] 到 out；設 i = i + 1
當 j < 長度(right)
    加入 right[j] 到 out；設 j = j + 1
傳回 out

合併_while_do(left, right)   // 示範 do while：至少合併 1 次
如果 長度(left) = 0
    傳回 right
如果 長度(right) = 0
    傳回 left
設 i = 0
設 j = 0
設 out = 空陣列
執行
    如果 left[i] <= right[j]
        加入 left[i] 到 out；設 i = i + 1
    否則
        加入 right[j] 到 out；設 j = j + 1
當 i < 長度(left) 並且 j < 長度(right)
（其後把 left 或 right 剩餘元素加入 out）
傳回 out

合併_until(left, right)   // 示範 repeat until：直至其中一邊用盡
如果 長度(left) = 0
    傳回 right
如果 長度(right) = 0
    傳回 left
設 i = 0
設 j = 0
設 out = 空陣列
重覆
    如果 left[i] <= right[j]
        加入 left[i] 到 out；設 i = i + 1
    否則
        加入 right[j] 到 out；設 j = j + 1
直至 i = 長度(left) 或 j = 長度(right)
（其後把 left 或 right 剩餘元素加入 out）
傳回 out

Check Point：小測／小遊戲（合併排序法）

（請按「下一題」開始）

得分：0 / 0

快速排序法（Quick Sort）﹙增潤部份﹚

重點

選一個 pivot（樞紐）把資料分成「比 pivot 小 / 等於 / 比 pivot 大」三部分，再遞歸處理兩邊。

Python 小練習：先做分割（partition）

先學會分割，你就掌握了快速排序法的核心一步。
A = [29, 10, 14, 37, 13] pivot = 14 left = [x for x in A if x < pivot] equal = [x for x in A if x == pivot] right = [x for x in A if x > pivot] print("pivot =", pivot) print("left =", left) print("equal =", equal) print("right =", right)
平均時間複雜度約為 O(n log n)；如果 pivot 分得平均，遞歸深度較淺，通常很快。

Python 小練習：一次實驗量度遞歸深度（random pivot）

這只是一次隨機實驗；你可以多跑幾次，或把資料量改大，觀察深度變化。
import random def quick_sort_depth(A): # 傳回 (sorted_list, max_depth) if len(A) <= 1: return A[:], 1 pivot = random.choice(A) left = [x for x in A if x < pivot] equal = [x for x in A if x == pivot] right = [x for x in A if x > pivot] L, d1 = quick_sort_depth(left) R, d2 = quick_sort_depth(right) return L + equal + R, 1 + max(d1, d2) A = [random.randint(1, 99) for _ in range(16)] sorted_A, depth = quick_sort_depth(A) print("A =", A) print("sorted =", sorted_A) print("最大遞歸深度（一次實驗）=", depth)
最壞情況會退化到 O(n²)（例如 pivot 選得很差、資料已排序）；因此 pivot 選擇很重要。

Python 小練習：已排序資料 + 固定用第一個 pivot（示範最壞情況）

已排序資料若每次都選第一個做 pivot，會令其中一邊幾乎是空，遞歸深度接近 n。
def quick_sort_first_pivot_depth(A): if len(A) <= 1: return 1 pivot = A[0] left = [x for x in A[1:] if x < pivot] right = [x for x in A[1:] if x >= pivot] return 1 + max(quick_sort_first_pivot_depth(left), quick_sort_first_pivot_depth(right)) A = list(range(1, 11)) # 已排序 depth = quick_sort_first_pivot_depth(A) print("A 已排序：", A) print("固定用第一個 pivot，最大遞歸深度 =", depth)

快速排序法的名字之所以叫「快速」，不是因為它每一步都很簡單，而是因為它在平均情況下能很有效地把資料分開，令每次遞歸處理的範圍都大幅縮小，從而在大多數情況下表現出色。

學習快速排序法時，你最少要掌握「pivot 令資料分成兩邊」這個核心概念。至於 partition 的細節（不同指標寫法）可以先選一種熟悉的版本練熟，確保你能用追蹤表說明每一步指標如何移動。

此外，你應建立正確的期望：快速排序法並非永遠最快，它存在最壞情況退化。但由於最壞情況並不常見，加上它常可原地分割、記憶體額外需求較低，因此在許多實務系統中仍然非常常用。

互動示範：快速排序法（100 個數據，10×10 顯示）

快速排序法的示範預設使用 100 個數據（10×10 排列）。你可以切換不同版本（本節下方有三種版本的程式與原理），並用標記觀察 partition 的移動與交換。

🎮 小遊戲：Quick Sort（pivot 三路分割概念）

圖像化例子：快速排序法的分割概念

示例陣列：[8, 4, 7, 3, 1, 9, 2]，以 pivot = 7 為例。

一次分割（概念）：
left  : [4, 3, 1, 2]   （< pivot）
mid   : [7]            （= pivot）
right : [8, 9]         （> pivot）

之後分別對 left / right 做遞歸排序，再把結果接回一起。

版本	是否原地（in-place）	分割點特性	備註
三區分割	否（需額外列表）	直接得到 left/mid/right	易讀，對重複值友善
Lomuto	是	傳回 pivot 的最終位置	程式較直觀；pivot 選得差時易退化
Hoare	是	傳回分割邊界（不一定是 pivot 位置）	交換較少；遞歸區間與 Lomuto 不同

示例：偽代碼 ↔ Python（4 種偽代碼循環 + 2 種 Python 寫法）

此處示範三個常見版本：三區分割（left/mid/right）、Lomuto 分割、Hoare 分割。可在不同版本之間比較「pivot 選擇、交換方式、返回的分割點」。

特點：一次掃描把資料分成 left / mid / right 三段，易讀，對重複值較友善。

代價：需要額外列表，空間較高（非原地）。

快速排序法(A)
如果 長度(A) <= 1
    傳回 A
設 pivot = A[0]
設 left = 空陣列
設 equal = 空陣列
設 right = 空陣列
設 i 由 0至 長度(A)-1
    如果 A[i] < pivot
        加入 A[i] 到 left
    否則如果 A[i] > pivot
        加入 A[i] 到 right
    否則
        加入 A[i] 到 equal
傳回 快速排序法(left) + equal + 快速排序法(right)

快速排序法_inplace(A, low, high)
設 i = low
設 j = high
設 pivot = A[(low + high) 整除 2]
當 i <= j
    當 A[i] < pivot
        設 i = i + 1
    當 A[j] > pivot
        設 j = j - 1
    如果 i <= j
        交換 A[i] 與 A[j]
        設 i = i + 1
        設 j = j - 1
如果 low < j
    快速排序法_inplace(A, low, j)
如果 i < high
    快速排序法_inplace(A, i, high)

分割_Hoare(A, low, high)   // 示範 do while（指標掃描）
設 pivot = A[(low + high) 整除 2]
設 i = low - 1
設 j = high + 1
執行
    執行
        設 i = i + 1
    當 A[i] < pivot
    執行
        設 j = j - 1
    當 A[j] > pivot
    如果 i >= j
        傳回 j
    交換 A[i] 與 A[j]
當 true

分割_repeat(A, low, high)  // 示範 repeat until（直至 i >= j）
設 pivot = A[(low + high) 整除 2]
設 i = low
設 j = high
重覆
    當 A[i] < pivot
        設 i = i + 1
    當 A[j] > pivot
        設 j = j - 1
    如果 i < j
        交換 A[i] 與 A[j]
        設 i = i + 1
        設 j = j - 1
直至 i >= j
傳回 j

特點：以 A[high] 作 pivot，掃描一次把 <= pivot 的放左邊，最後把 pivot 放到正確位置。

注意：在已排序/近似排序且 pivot 選得不好時，可能退化。

快速排序_Lomuto(A, low, high)
如果 low >= high 則
    傳回
設 p = Lomuto分割(A, low, high)
快速排序_Lomuto(A, low, p - 1)
快速排序_Lomuto(A, p + 1, high)

Lomuto分割(A, low, high)
設 pivot = A[high]
設 i = low - 1
設 j 由 low 至 high - 1
    如果 A[j] <= pivot 則
        i = i + 1
        交換 A[i] 與 A[j]
交換 A[i + 1] 與 A[high]
傳回 i + 1

快速排序_Lomuto(A, low, high)
如果 low >= high 則
    傳回
設 p = Lomuto分割(A, low, high)
快速排序_Lomuto(A, low, p - 1)
快速排序_Lomuto(A, p + 1, high)

Lomuto分割(A, low, high)
設 pivot = A[high]
設 i = low - 1
設 j = low
當 j <= high - 1
    如果 A[j] <= pivot 則
        i = i + 1
        交換 A[i] 與 A[j]
    j = j + 1
交換 A[i + 1] 與 A[high]
傳回 i + 1

快速排序_Lomuto(A, low, high)
如果 low >= high 則
    傳回
設 p = Lomuto分割(A, low, high)
快速排序_Lomuto(A, low, p - 1)
快速排序_Lomuto(A, p + 1, high)

Lomuto分割(A, low, high)
設 pivot = A[high]
設 i = low - 1
設 j = low
執行
    如果 A[j] <= pivot 則
        i = i + 1
        交換 A[i] 與 A[j]
    j = j + 1
當 j <= high - 1
交換 A[i + 1] 與 A[high]
傳回 i + 1

快速排序_Lomuto(A, low, high)
如果 low >= high 則
    傳回
設 p = Lomuto分割(A, low, high)
快速排序_Lomuto(A, low, p - 1)
快速排序_Lomuto(A, p + 1, high)

Lomuto分割(A, low, high)
設 pivot = A[high]
設 i = low - 1
設 j = low
重覆
    如果 A[j] <= pivot 則
        i = i + 1
        交換 A[i] 與 A[j]
    j = j + 1
直至 j > high - 1
交換 A[i + 1] 與 A[high]
傳回 i + 1

特點：左右指針向內收縮，交換「放錯邊」的元素；返回的分割點不一定是 pivot 最終位置。

注意：遞歸區間為 [low, p] 與 [p+1, high]（與 Lomuto 不同）。

快速排序_Hoare(A, low, high)
如果 low >= high 則
    傳回
設 p = Hoare分割(A, low, high)
快速排序_Hoare(A, low, p)
快速排序_Hoare(A, p + 1, high)

Hoare分割(A, low, high)
設 pivot = A[(low + high) div 2]
設 i = low - 1
設 j = high + 1
設 t 由 1 至 (high - low + 1)
    重覆
        i = i + 1
    直至 A[i] >= pivot
    重覆
        j = j - 1
    直至 A[j] <= pivot
    如果 i >= j 則
        傳回 j
    交換 A[i] 與 A[j]

快速排序_Hoare(A, low, high)
如果 low >= high 則
    傳回
設 p = Hoare分割(A, low, high)
快速排序_Hoare(A, low, p)
快速排序_Hoare(A, p + 1, high)

Hoare分割(A, low, high)
設 pivot = A[(low + high) div 2]
設 i = low - 1
設 j = high + 1
當 True
    重覆
        i = i + 1
    直至 A[i] >= pivot
    重覆
        j = j - 1
    直至 A[j] <= pivot
    如果 i >= j 則
        傳回 j
    交換 A[i] 與 A[j]

快速排序_Hoare(A, low, high)
如果 low >= high 則
    傳回
設 p = Hoare分割(A, low, high)
快速排序_Hoare(A, low, p)
快速排序_Hoare(A, p + 1, high)

Hoare分割(A, low, high)
設 pivot = A[(low + high) div 2]
設 i = low - 1
設 j = high + 1
執行
    重覆
        i = i + 1
    直至 A[i] >= pivot
    重覆
        j = j - 1
    直至 A[j] <= pivot
    如果 i < j 則
        交換 A[i] 與 A[j]
當 i < j
傳回 j

快速排序_Hoare(A, low, high)
如果 low >= high 則
    傳回
設 p = Hoare分割(A, low, high)
快速排序_Hoare(A, low, p)
快速排序_Hoare(A, p + 1, high)

Hoare分割(A, low, high)
設 pivot = A[(low + high) div 2]
設 i = low - 1
設 j = high + 1
重覆
    重覆
        i = i + 1
    直至 A[i] >= pivot
    重覆
        j = j - 1
    直至 A[j] <= pivot
    如果 i < j 則
        交換 A[i] 與 A[j]
直至 i >= j
傳回 j

Check Point：小測／小遊戲（快速排序法）

（請按「下一題」開始）

得分：0 / 0

計數排序法（Counting Sort）﹙增潤部份﹚

重點

計數排序法不是「比較排序」，而是先統計每個值出現的次數，再重建排序結果。

Python 小練習：建立頻率表
a = [4, 2, 2, 8, 3, 3, 1] k = 8 count = [0] * (k + 1) # TODO：用 for loop 把每個值的次數加到 count # 最後印出 count
當值域大小為 k 時，時間複雜度約為 O(n + k)；如果 k 很大，反而會變慢且佔用記憶體。

Python 小練習：比較 n 與 k 的大小
n = 20 k_small = 50 k_large = 10_000_000 # TODO：用 print 說明：當 k 遠大於 n 時，count 陣列會很大（記憶體成本高）
若使用「前綴和 + 由後向前放置」，計數排序法可以做到穩定排序（常用於基數排序法的子程序）。

Python 小練習：觀察穩定性（保持相同 key 的相對次序）
# 每個元素是 (key, tag)；希望排序後 key 相同時 tag 的先後不變 items = [(2,'A'), (1,'B'), (2,'C'), (1,'D')] # TODO：思考：若只按 key 排序，如何保持 A 在 C 之前、B 在 D 之前？ # （提示：穩定排序的定義）
計數排序法適用於離散且範圍不大的整數，例如：分數（0–100）、年齡（0–120）、等級（1–10）。

Python 小練習：把 0–100 的分數排序
scores = [55, 100, 72, 72, 18, 90, 0, 37] # TODO：用計數排序思想把 scores 排序（可先寫出 count，再重建）

計數排序法（Counting Sort）是一種非比較排序，透過統計每個值的出現次數來完成排序。

適用於整數且值域（range）不大時，速度非常快。

建立頻率陣列 count，記錄每個值出現次數。
（可選）把 count 轉成前綴和，得到「位置資訊」。
重建輸出：按次數把值放回（或用前綴和穩定地放回）。

典型複雜度：時間 O(n+k)，空間 O(k)。

若分數只介乎 0–100，就可以建立長度 101 的 count 陣列，快速統計後重建。

排序法	是否比較排序	時間（典型）	限制
計數排序	否	O(n+k)	值域 k 不能太大
快速排序	是	平均 O(n log n)	最壞可 O(n²)

把計數排序當作通用排序：若資料不是小範圍整數，計數排序不適用。
忽略記憶體成本：k 很大時，count 陣列會消耗大量記憶體。
要穩定卻只用「按次數輸出」：若要穩定，需前綴和 + 由後向前放置。

在「值域不大」的情況下，計數排序法往往比 O(n log n) 的比較排序更快，因為它避免了大量元素比較。

它的速度來自兩個線性階段：一次掃描統計、一次掃描重建。但代價是需要一個與值域大小成正比的 count 陣列。

互動示範：計數排序法（100 個數據，10×10 顯示）

計數排序法會先建立「出現次數」的頻率表（count），再重建排序後的輸出。你可以選擇排序方向，並觀察「數到幾多個」如何變成「排好序的結果」。

🎮 小遊戲：Counting Sort（放入計數桶）

圖像化：頻率表（count）如何重建排序結果

例子：A=[4,2,2,8,3,3,1]、k=8

count 索引: 0 1 2 3 4 5 6 7 8
count 次數:  0 1 2 2 1 0 0 0 1

重建輸出：
1 出現 1 次 → [1]
2 出現 2 次 → [1,2,2]
3 出現 2 次 → [1,2,2,3,3]
4 出現 1 次 → [1,2,2,3,3,4]
8 出現 1 次 → [1,2,2,3,3,4,8]

程式示例：不同版本（可切換）

版本 A 著重概念；版本 B 展示穩定性與負數處理。

適用於值域不大（0..k）的整數資料。核心是「用 count 記錄每個值出現次數」。

計數排序(A, k)
# A 內的值介乎 0..k（非負整數）

設 count[0..k] = 0
設 i 由 0 至 長度(A) - 1
    count[A[i]] = count[A[i]] + 1

設 output = 空列表
設 v 由 0 至 k
    設 c 由 1 至 count[v]
        將 v 加入 output

傳回 output

計數排序(A, k)
設 count[0..k] = 0
設 i = 0
當 i < 長度(A)
    count[A[i]] = count[A[i]] + 1
    i = i + 1

設 output = 空列表
設 v = 0
當 v <= k
    設 c = 1
    當 c <= count[v]
        將 v 加入 output
        c = c + 1
    v = v + 1

傳回 output

計數排序(A, k)
設 count[0..k] = 0
設 i = 0
執行
    count[A[i]] = count[A[i]] + 1
    i = i + 1
當 i < 長度(A)

設 output = 空列表
設 v = 0
執行
    設 c = 1
    執行
        如果 c > count[v] 則 跳出
        將 v 加入 output
        c = c + 1
    當 True
    v = v + 1
當 v <= k

傳回 output

計數排序(A, k)
設 count[0..k] = 0
設 i = 0
重覆
    count[A[i]] = count[A[i]] + 1
    i = i + 1
直至 i == 長度(A)

設 output = 空列表
設 v = 0
重覆
    設 c = 1
    重覆
        如果 c > count[v] 則 跳出
        將 v 加入 output
        c = c + 1
    直至 False
    v = v + 1
直至 v == k + 1

傳回 output

加入 offset 把負數平移；再用前綴和 + 由後向前放置，確保穩定排序。

計數排序_穩定_含負數(A)
# 允許負數：用 offset 把值平移到 0..k

設 minV = 最小值(A)
設 maxV = 最大值(A)
設 offset = -minV
設 k = maxV - minV

設 count[0..k] = 0
設 i 由 0 至 長度(A) - 1
    count[A[i] + offset] = count[A[i] + offset] + 1

# 前綴和：count[v] 變成「<= v 的元素總數」
設 v 由 1 至 k
    count[v] = count[v] + count[v - 1]

設 output[0..長度(A)-1]
設 i 由 長度(A) - 1 至 0
    設 v = A[i] + offset
    count[v] = count[v] - 1
    output[count[v]] = A[i]

傳回 output

計數排序_穩定_含負數(A)
設 minV = 最小值(A)
設 maxV = 最大值(A)
設 offset = -minV
設 k = maxV - minV

設 count[0..k] = 0
設 i = 0
當 i < 長度(A)
    count[A[i] + offset] = count[A[i] + offset] + 1
    i = i + 1

設 v = 1
當 v <= k
    count[v] = count[v] + count[v - 1]
    v = v + 1

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
當 i >= 0
    設 v = A[i] + offset
    count[v] = count[v] - 1
    output[count[v]] = A[i]
    i = i - 1

傳回 output

計數排序_穩定_含負數(A)
設 minV = 最小值(A)
設 maxV = 最大值(A)
設 offset = -minV
設 k = maxV - minV

設 count[0..k] = 0
設 i = 0
執行
    count[A[i] + offset] = count[A[i] + offset] + 1
    i = i + 1
當 i < 長度(A)

設 v = 1
執行
    count[v] = count[v] + count[v - 1]
    v = v + 1
當 v <= k

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
執行
    設 val = A[i] + offset
    count[val] = count[val] - 1
    output[count[val]] = A[i]
    i = i - 1
當 i >= 0

傳回 output

計數排序_穩定_含負數(A)
設 minV = 最小值(A)
設 maxV = 最大值(A)
設 offset = -minV
設 k = maxV - minV

設 count[0..k] = 0
設 i = 0
重覆
    count[A[i] + offset] = count[A[i] + offset] + 1
    i = i + 1
直至 i == 長度(A)

設 v = 1
重覆
    count[v] = count[v] + count[v - 1]
    v = v + 1
直至 v == k + 1

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
重覆
    設 val = A[i] + offset
    count[val] = count[val] - 1
    output[count[val]] = A[i]
    i = i - 1
直至 i == -1

傳回 output

Check Point：計數排序法

（載入中…）

基數排序法（Radix Sort）﹙增潤部份﹚

重點

基數排序法會「逐位（digit）」排序（常見是由低位到高位 LSD），每一輪都用一個穩定排序處理該位。

Python 小練習：取得某個數的個位 / 十位
x = 802 # TODO：印出 x 的個位、十位、百位 # 提示：用 // 和 %
若每一位的子排序是穩定的，最終結果才會正確；因此常用「穩定計數排序」作為子程序。

Python 小練習：思考穩定性的重要性
# 思考題（不一定要寫程式）： # 若先按「個位」排序，再按「十位」排序， # 為何第二輪必須是穩定排序，才能保留第一輪的成果？
典型複雜度：若每輪是 O(n+k)，總輪數為 d（位數），則整體約為 O(d*(n+k))；當 d 不大時非常快。

Python 小練習：估算位數 d
data = [170, 45, 75, 90, 802, 24, 2, 66] max_v = max(data) # TODO：計算 max_v 的位數 d（可用 len(str(max_v))） # 並說明：radix sort 需要做幾輪？
適合固定長度的整數或字串（例如身份證號碼、日期碼、固定長度代碼），不適合任意精度浮點或超長字串直接使用。

Python 小練習：把固定長度字串按字元排序（概念）
codes = ["B12", "A02", "A10", "B01"] # TODO：思考：若每個位置都用穩定排序（由最後一個字元到第一個字元）， # 是否能把 codes 排序？（提示：這是字串的 radix sort 思路）

基數排序法（Radix Sort）是一種把資料按「位」（digit/character position）逐步排序的非比較排序。

常見為 LSD（由低位到高位）。

選定基底（base），例如 base 10（十進制）或 base 256（byte）。
從最低位開始，對該位做一次穩定排序。
重複到最高位，得到整體排序結果。

核心：每一輪必須穩定，否則上一輪的排序資訊會被破壞。

資料：[170, 45, 75, 90, 802, 24, 2, 66]

第 1 輪按個位排序，第 2 輪按十位排序，第 3 輪按百位排序（LSD）。

方法	是否比較排序	依賴條件	典型應用
基數排序	否	位數 d 不大；可分解為位	整數、固定長度字串
計數排序	否	值域 k 不大	分數、年齡、等級

子排序不穩定：會破壞前一輪結果。
忽略基底選擇：base 太小輪數多，base 太大每輪成本上升。
把 radix sort 當作「任何資料都可以用」：它需要能拆成「位」的表示法。

基數排序法常被視為「非常快」的排序法之一，原因是它把排序拆成多輪較簡單的子排序（例如計數排序），每輪都可以做到線性級別。

若位數 d 不大（例如 32-bit 整數最多 4 個 byte 或 10 進制約 10 位以內），總輪數很少，因此整體速度往往非常理想。

互動示範：基數排序法（100 個數據，10×10 顯示）

基數排序法（LSD）會由個位開始，逐位（十位、百位……）進行穩定排序。你可以觀察每一輪「按位數分桶」如何逐步得到完全排序的結果。

🎮 小遊戲：Radix Sort（逐位放桶）

圖像化：LSD（由低位到高位）

以 802、170、90 為例（十進制 LSD）：
第 1 輪（個位）：802(2), 170(0), 90(0) → 先按個位排
第 2 輪（十位）：802(0), 170(7), 90(9) → 再按十位排（必須穩定）
第 3 輪（百位）：802(8), 170(1), 90(0) → 最後按百位排

程式示例：不同版本（可切換）

版本 A 以 base 10 展示概念；版本 B 以 base 256 展示較底層的思路。

每一輪按「某一位 digit」做一次穩定排序（常用計數排序），由低位到高位。

基數排序_LSD(A)
# 以 10 進制、由低位到高位（LSD）排序

設 maxV = 最大值(A)
設 d = 位數(maxV)
設 exp = 1

設 t 由 1 至 d
    A = 依位計數排序(A, exp)
    exp = exp * 10

傳回 A

依位計數排序(A, exp)
設 count[0..9] = 0
設 i 由 0 至 長度(A) - 1
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] + 1

設 v 由 1 至 9
    count[v] = count[v] + count[v - 1]

設 output[0..長度(A)-1]
設 i 由 長度(A) - 1 至 0
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] - 1
    output[count[digit]] = A[i]

傳回 output

基數排序_LSD(A)
設 maxV = 最大值(A)
設 exp = 1
當 exp <= maxV
    A = 依位計數排序(A, exp)
    exp = exp * 10
傳回 A

依位計數排序(A, exp)
設 count[0..9] = 0
設 i = 0
當 i < 長度(A)
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] + 1
    i = i + 1

設 v = 1
當 v <= 9
    count[v] = count[v] + count[v - 1]
    v = v + 1

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
當 i >= 0
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] - 1
    output[count[digit]] = A[i]
    i = i - 1

傳回 output

基數排序_LSD(A)
設 maxV = 最大值(A)
設 exp = 1
執行
    A = 依位計數排序(A, exp)
    exp = exp * 10
當 exp <= maxV
傳回 A

依位計數排序(A, exp)
設 count[0..9] = 0
設 i = 0
執行
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] + 1
    i = i + 1
當 i < 長度(A)

設 v = 1
執行
    count[v] = count[v] + count[v - 1]
    v = v + 1
當 v <= 9

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
執行
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] - 1
    output[count[digit]] = A[i]
    i = i - 1
當 i >= 0

傳回 output

基數排序_LSD(A)
設 maxV = 最大值(A)
設 exp = 1
重覆
    A = 依位計數排序(A, exp)
    exp = exp * 10
直至 exp > maxV
傳回 A

依位計數排序(A, exp)
設 count[0..9] = 0
設 i = 0
重覆
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] + 1
    i = i + 1
直至 i == 長度(A)

設 v = 1
重覆
    count[v] = count[v] + count[v - 1]
    v = v + 1
直至 v == 10

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
重覆
    設 digit = (A[i] div exp) mod 10
    count[digit] = count[digit] - 1
    output[count[digit]] = A[i]
    i = i - 1
直至 i == -1

傳回 output

以 byte 為單位（0..255）處理，輪數較少，常見於底層實作；概念與版本 A 相同。

基數排序_Byte(A)
# 以 256 為基底（每次處理 8 bit），由低位到高位

設 shift = 0
設 t 由 1 至 4        # 32-bit 整數 → 4 個 byte
    A = 依位計數排序_Byte(A, shift)
    shift = shift + 8
傳回 A

依位計數排序_Byte(A, shift)
設 count[0..255] = 0
設 i 由 0 至 長度(A) - 1
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] + 1

設 v 由 1 至 255
    count[v] = count[v] + count[v - 1]

設 output[0..長度(A)-1]
設 i 由 長度(A) - 1 至 0
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] - 1
    output[count[byte]] = A[i]

傳回 output

基數排序_Byte(A)
設 shift = 0
當 shift < 32
    A = 依位計數排序_Byte(A, shift)
    shift = shift + 8
傳回 A

依位計數排序_Byte(A, shift)
設 count[0..255] = 0
設 i = 0
當 i < 長度(A)
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] + 1
    i = i + 1

設 v = 1
當 v <= 255
    count[v] = count[v] + count[v - 1]
    v = v + 1

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
當 i >= 0
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] - 1
    output[count[byte]] = A[i]
    i = i - 1

傳回 output

基數排序_Byte(A)
設 shift = 0
執行
    A = 依位計數排序_Byte(A, shift)
    shift = shift + 8
當 shift < 32
傳回 A

依位計數排序_Byte(A, shift)
設 count[0..255] = 0
設 i = 0
執行
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] + 1
    i = i + 1
當 i < 長度(A)

設 v = 1
執行
    count[v] = count[v] + count[v - 1]
    v = v + 1
當 v <= 255

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
執行
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] - 1
    output[count[byte]] = A[i]
    i = i - 1
當 i >= 0

傳回 output

基數排序_Byte(A)
設 shift = 0
重覆
    A = 依位計數排序_Byte(A, shift)
    shift = shift + 8
直至 shift == 32
傳回 A

依位計數排序_Byte(A, shift)
設 count[0..255] = 0
設 i = 0
重覆
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] + 1
    i = i + 1
直至 i == 長度(A)

設 v = 1
重覆
    count[v] = count[v] + count[v - 1]
    v = v + 1
直至 v == 256

設 output[0..長度(A)-1]
設 i = 長度(A) - 1
重覆
    設 byte = (A[i] >> shift) AND 255
    count[byte] = count[byte] - 1
    output[count[byte]] = A[i]
    i = i - 1
直至 i == -1

傳回 output

Check Point：基數排序法

（載入中…）

Python 練習：除錯與填空（按算法分組）

重點

每種算法提供 5–6 題「除錯／填空」練習：由 1–2 行開始，逐步增加到 最多約 5 行。
練習的目標不是背答案，而是建立習慣：追蹤變量 → 找出錯誤位置 → 修正 → 再測試。
大部分題目要求你只輸出指定結果（例如索引或排序後的數列），方便自動批改。

除錯／填空（5 題）

自行實作（1 題）

總結比較：如何選擇檢索與排序？

重點

不同方法的效率主要由時間複雜度（例如 O(n)、O(n log n)、O(n²)）描述。

Python 小練習：用表格比較成長速度

以下用簡單估算比較三種增長速度。留意：n 變大時，n² 會急速變得很大。
import math print("n | O(n) | O(n log2 n) | O(n^2)") print("--|------|------------|-------") for n in [10, 100, 1000]: on = n onlogn = int(n * math.log(n, 2)) on2 = n * n print(n, "|", on, "|", onlogn, "|", on2)
除速度外，也要考慮：是否需要額外記憶體、是否穩定排序、以及是否容易實作／除錯。

Python 小練習：比較「原地排序」與「傳回新排序結果」

A.sort() 會直接改動原本陣列；sorted(A) 會傳回新陣列。
A = [3, 1, 2] B = sorted(A) # 傳回新 list print("sorted(A) 後：A =", A, "| B =", B) A.sort() # 原地排序 print("A.sort() 後：A =", A)
選擇方法時可用一個簡單準則：資料小／無序 → 線性檢索；資料已排序且很大 → 對分檢索；排序方面，視資料特性選擇合併排序法／快速排序法等。

Python 小練習：比較線性檢索 vs 對分檢索的「最壞步數」

下面只做「步數估算」：線性檢索最壞是 n；對分檢索最壞大約是 log₂(n)+1。
def worst_steps_linear(n): return n def worst_steps_binary(n): low = 0 high = n - 1 steps = 0 while low <= high: steps += 1 mid = (low + high) // 2 low = mid + 1 return steps for n in [10, 100, 1000, 1000000]: print("n =", n, "| 線性檢索最壞步數 =", worst_steps_linear(n), "| 對分檢索最壞步數 ≈", worst_steps_binary(n))

定義

在比較算法時，我們常用時間複雜度描述「當輸入規模 n 變大時，步驟數大約如何成長」。常見寫法是 Big‑O（例如 O(n)、O(n²)、O(n log n)）。

你可以把它理解成：

O(n)：n 變 10 倍，步驟大約變 10 倍。
O(n²)：n 變 10 倍，步驟大約變 100 倍。
O(log n)：n 變很大，步驟只會慢慢增加。

重點：Big‑O 是「趨勢」，不是精確步數；它幫你比較「規模變大時」誰更能撐得住。

比較（概念表）

算法	類型	前提 / 適用條件	時間（平均）	時間（最壞）	額外空間	重點備註
線性檢索	檢索	無（可用於未排序資料）	O(n)	O(n)	O(1)	最直觀；小資料或一次性查找可接受
對分檢索	檢索	資料必須已排序（且可隨機存取）	O(log n)	O(log n)	O(1)	穩定快速；適合有序資料
雜湊檢索	檢索	需要雜湊函數；需處理碰撞	平均 O(1)	O(n)	O(n)	適合大量「是否存在」查找；不保序、不擅長範圍查詢
插值檢索	檢索	已排序；分佈相對均勻較有利	理想 O(log log n)	O(n)	O(1)	可能比對分快；但估算失真會退化
選擇排序	排序	無	O(n²)	O(n²)	O(1)	交換次數少；但比較次數固定偏多
插入排序	排序	無；近乎排序時特別快	平均 O(n²)	O(n²)	O(1)	近乎排序時可接近 O(n)；穩定
冒泡排序	排序	無	平均 O(n²)	O(n²)	O(1)	可加「無交換即停止」優化；穩定
合併排序	排序	無	O(n log n)	O(n log n)	O(n)	穩定；適合大資料；需要額外陣列
快速排序	排序	無（但 pivot 選擇影響效能）	平均 O(n log n)	O(n²)	O(log n)（遞歸棧）	通常最快之一；版本多（Lomuto/Hoare/三區分割）
計數排序	排序	資料為整數且值域 k 不大	O(n + k)	O(n + k)	O(k)	非常快；可做穩定排序（前綴和）
基數排序	排序	可分解為位（digit/byte）；子排序需穩定	O(d*(n + k))	O(d*(n + k))	通常 O(n + k)	固定長度資料很快；常用計數排序作子程序

表格是「常見情況」總結；不同實作（例如 pivot 選法）會影響細節，但不改變核心概念。

常見錯誤

只背「對分檢索很快」，但忘記前提是資料必須已排序。
把所有排序法都當成「兩層迴圈」而忽略結構差異（例如合併排序法的遞歸與合併）。
只記 Big‑O，不懂它代表「規模變大時」的趨勢，答題時說不出原因。

答題策略：先說「流程」，再說「限制／前提」，最後補「效率（時間／空間）」。

如果你只想用一句話記住選擇方法的思路，可以這樣想：資料未排序而且只做少量查找 → 線性檢索；資料已排序 → 對分檢索；需要大量「是否存在」查找 → 雜湊檢索；資料已排序且分佈較均勻 → 插值檢索；資料量大的一般排序 → 合併排序或快速排序；資料幾乎已排序 → 插入排序通常更合適；值域很小的整數 → 計數排序；固定長度整數/字串 → 基數排序。

最重要的是，你要能用追蹤表把流程說清楚：例如在對分檢索中每次 low/high 如何更新；在合併排序法中左右半邊如何合併；在快速排序法中 pivot 如何把資料分割。只要你能清楚描述流程，很多題目自然就能解。