定義和問題

問題描述：在未排序陣列 $A$（含 $n$ 個互異元素）中，找出第 $k$ 小的元素，$1 \le k \le n$
輸入：$A$、$k$
輸出：$A$ 的第 $k$ 小元素
特例：
- 最小值：$k=1$
- 最大值：$k=n$
- 中位數：$k \approx \frac{n}{2}$（較能抵抗極端值）
核心問題：能否在不完整排序下，比排序更快地找到第 $k$ 小元素
基線解：排序 $A$ 需 $\mathcal{O}(n\log n)$，取第 $k$ 個為 $\mathcal{O}(1)$，總計 $\mathcal{O}(n\log n)$
為何可更快：
- 比較模型中，排序下限 $\Omega(n\log n)$
- 選擇問題嚴格更容易，可望低於 $\mathcal{O}(n\log n)$
- 目標：線性時間 $\mathcal{O}(n)$（至少需讀過每個元素一次）
設計要點：分割與遞迴（divide and conquer），只做與序位相關的部分工作，避免完整排序

方法

方法 1｜同時計算最小與最大值（Pairwise 成對法）

問題定義：給定長度 $n$ 的陣列 $A$，同時計算 $\min(A)$ 與 $\max(A)$，使比較次數最少
經典天真法（對照）：
- 分別線性掃描兩次：$(n-1)$ 次求 $\min$，再 $(n-1)$ 次求 $\max$
- 比較次數：$2n-2$
成對法（最佳）：
- 核心：兩兩成對。先在對內比較一次，較小者只與 $min$ 比，較大者只與 $max$ 比
- 演算法：
  - 初始化：
    - $n$ 為奇數：$min = max = A[0]$，從索引 $1$ 起成對
    - $n$ 為偶數：先比 $A[0]$ 與 $A[1]$（次）；小者給 $min$，大者給 $max$，從索引 $2$ 起成對
  - 成對處理：每對 $(x,y)$
    - 先比 $x$ 對 $y$（$1$ 次）
    - 較小者對 $min$（$1$ 次）；較大者對 $max$（$1$ 次）
    - 每對固定 $3$ 次比較
  - 掃描結束輸出 $(min,;max)$
比較次數分析：
- $n$ 為偶數：$1 + 3\Big(\frac{n}{2}-1\Big) = \frac{3n}{2}-2$
- $n$ 為奇數：$3\Big\lfloor \frac{n}{2} \Big\rfloor$
- 統一上界：$\le 3\Big\lfloor \frac{n}{2} \Big\rfloor$
最優性（下界）：
- 對抗者或決策樹可證：同時計算 $\min,\max$ 至少需 $\lceil 3n/2 \rceil - 2$ 次比較
- 成對法達到該下界，於比較模型中最優
正確性不變量：
- 任一時刻，min 為已處理元素之最小值，max 為最大值
- 對內先比較保證只把「較小者」拿去與 $min$ 比、「較大者」拿去與 $max$ 比

pseudocode：

PAIRWISE-MIN-MAX(A)
  n ← length(A)
  if n == 1: return (A[0], A[0])
  if n is even:
    if A[0] < A[1]: min ← A[0]; max ← A[1]
    else:           min ← A[1]; max ← A[0]
    i ← 2
  else:
    min ← A[0]; max ← A[0]
    i ← 1
  while i ≤ n-2:
    x ← A[i]; y ← A[i+1]
    if x < y:
      if x < min: min ← x
      if y > max: max ← y
    else:
      if y < min: min ← y
      if x > max: max ← x
    i ← i + 2
  return (min, max)

方法 2｜Randomized-Select

命名核心：==每次遞迴都隨機選 pivot。隨機性不是實作細節，而是演算法本質，並且使用 quick sort 裡面的類似 partition 方法，因為 pivot 是隨機==。
與確定性法的區別：
- Randomized-Select：隨機等機率選 pivot。放棄最壞情況保證，換得簡單與平均表現。
效能模型由隨機性決定：
- 最壞情況：若連續選到極端 pivot，時間 $O(n^2)$。
- 期望情況：有約 $1/2$ 機率選到「好 pivot」，使規模 $\le \tfrac{3}{4}n$；平均僅需約兩次即可遇到好 pivot，整體期望時間 $O(n)$。
實務優勢：
- 簡單：實作容易。
- 常數小：較少額外結構與計算，實測常快於 Median of Medians。
關鍵遞迴細節：
- 基底情況：若 $p=r$，子陣列 $A[p..r]$ 僅一元素，其秩為 $1$，直接回傳 $A[p]$。
- 秩調整 $i-k$：令 $q$ 為 pivot 位置，$k=q-p+1$ 為 pivot 在 $A[p..r]$ 的秩。
  - 若 $i<k$：在左半 $A[p..q-1]$ 找第 $i$ 小。
  - 若 $i=k$：回傳 $A[q]$。
  - 若 $i>k$：在右半 $A[q+1..r]$ 找第 $i’ = i-k$ 小（因左半含 pivot 的 $k$ 個元素皆 $\le$ pivot，已被排除）。
  - 迷你例：原目標第 $i=7$ 小，pivot 秩 $k=4$，改在右半找第 $i’=7-4=3$ 小。

Randomized-Select 分析

最佳情況（Best Case）
- 條件：每次 pivot 使目標落在另一側大小 $\le n/2$ 的子陣列（如接近中位）
- 遞迴式：$$T(n)=T\left(\tfrac{n}{2}\right)+cn$$
- 解（Master 定理 Case 3）：$$T(n)=\Theta(n)$$
- 直覺：每層 $O(n)$ 做一次 partition，規模對半，幾何級數收斂為線性
最差情況（Worst Case）
- 條件：每次 pivot 為最小或最大，只去掉 $1$ 個元素
- 遞迴式：$$T(n)=T(n-1)+cn$$
- 展開：
  $$
  \begin{aligned}
  T(n)&=T(1)+c\sum_{k=2}^{{n}k \
  
  &=T(1)+c\left(\tfrac{n(n+1)}{2}-1\right)
  
  =\Theta(n}2)
  \end{aligned}
  $$
- 對照：與 Quicksort 最壞遞迴同型，每層線性，層數近 $n$
期望情況（Expected / Average Case）
- 隨機化機制：每次 PARTITION 的 pivot 由均勻亂數選出；對固定輸入，時間為隨機變數 $T(n)$，求 $\mathbb{E}[T(n)]$
- 關鍵引理（CLRS 9.1）：
  - 定義「有幫助」切分：保留的子問題大小 $\le \tfrac{3}{4}$ 上一次
  - 當 pivot 落在中間一半（秩在 $\lceil n/4\rceil,\lfloor 3n/4\rfloor$）即為有幫助
  - 機率界：落在中間一半的機率 $\ge \tfrac{1}{2}$，平均約兩次切分就遇到一次有幫助
- 幾何衰減計數：
  - 以「世代」為單位：兩次有幫助切分之間的切分群
  - 第 $k$ 世代規模 $n_k\le (3/4)^k n$
  - 每次切分成本 $\le c,n_k$
- 期望總成本上界：
  $$
  \mathbb{E}[T(n)] \le c\sum_{k\ge0}\mathbb{E}[X_k]\cdot n_k,\quad \mathbb{E}[X_k]\le 2
  $$ $$
  \Rightarrow\ \mathbb{E}[T(n)] \le 2c,n\sum_{k\ge0}\left(\tfrac{3}{4}\right)^k = O(n)
  $$
  - CLRS 常數上界約 $<8n$；配合首層的 $\Omega(n)$，得 $\Theta(n)$
- 結論：$$\boxed{\ \mathbb{E}[T(n)]=\Theta(n)\ }$$

方法3｜Median of Medians

02-方法3 Median of Medians

目的在於提供一個 method 可以在 worst case 的時候還是 $O(n)$ 。
那他的方式或是原則就是小心選擇 pivot。

實現方法

03-實現方法

1. 分組：把當前子陣列切成 $5$ 人小組；最後一組可不足 $5$。一次線性掃描完成，$O(n)$，並且把 $p+1$ 往後因為最前面已經是最小的那幾個了所以 $i-1$
2. 組內排序：對每組 $5$ 個做就地排序（常用 insertion sort）。每組成本為常數，組數 $\lceil n/5\rceil$，合計 $O(n)$，順便計算有幾組 11 行，12~13 就是把 group 排序
3. 取得 median-of-medians 並分割：
- 設有效長度為 $n’$，組數 $g=\frac{n’}{5}$。各組中位數收集成連續切片 $A[p+2g,..,p+3g-1]$（長度 $g$）
- 在此切片上遞迴呼叫 SELECT 取其中位數 $x$（注意：不是因為已排序，而是對該切片做遞迴選取）
- 以值 $x$ 對整段 $A[p..r]$ 做 partition，得位置 $q$
4. 判斷方向：令 $k=q-p+1$
- 若 $i=k$：回傳 $x$
- 若 $i<k$：只在左側遞迴
- 若 $i>k$：只在右側遞迴，秩改為 $i-k$
要點：
- 每次進入 SELECT 都會重新分組與小排序（子問題範圍已改）
- 若長度非 $5$ 的倍數，可先剝掉至多 $4$ 個最小值（同步更新 $p\leftarrow p+1,\ i\leftarrow i-1$）
- 最壞情況複雜度遞迴：
  $$T(n)\ \le\ T\left(\left\lceil \tfrac{n}{5}\right\rceil\right)\ +\ T\left(\tfrac{7n}{10}+O(1)\right)\ +\ O(n)\ =\ O(n).$$

證明

以 $5$ 人一組並組內排序，取每組中位形成集合 $M$，令 $x=\mathrm{median}(M)$。
依定義，$M$ 中至少一半的組中位 $\ge x$（與遞迴方向無關）。
在每個這類「好組」中，因已排序，至少 3 個元素 $\ge x$（組中位本身及其右側兩個）。
需扣除至多 2 組 的例外：包含 $x$ 的那組，以及可能不足 $5$ 個元素的殘缺組。
因此，$\ge x$ 的元素數至少
$$
3\big(\lfloor \frac{|M|}{2}\rfloor-2\big)\ \ge\ \tfrac{3n}{10}-O(1),
$$
對稱地，$\le x$ 的元素數也至少 $\tfrac{3n}{10}-O(1)$。
於是以 $x$ 分割後，仍需遞迴的較大一側大小
$$
\le\ n-\Big(\tfrac{3n}{10}-O(1)\Big)\ =\ \tfrac{7n}{10}+O(1).
$$
導出最壞情況遞迴式
$$
T(n)\ \le\ T\left(\left\lceil \tfrac{n}{5}\right\rceil\right)\ +\ T\left(\tfrac{7n}{10}+O(1)\right)\ +\ O(n)\ =\ O(n).
$$

Total complex Time

04-Total complex Time

範例

資料：$A[p..r]=[22,7,18,11,25,9,14,6,20,13]$；$p=0$，$n=10=5g\Rightarrow g=2$
1) 分組＋組內排序（就地）（$j=0,1$）
- 組1：索引 $[j,j+g,j+2g,j+3g,j+4g]=[0,2,4,6,8]$
  值 $[22,18,25,14,20]\ \rightarrow$ 排序寫回 $\rightarrow\ [14,18,20,22,25]$
  組中位索引 $0+2g=4$，值 $20$
- 組2：索引 $[1,3,5,7,9]$
  值 $[7,11,9,6,13]\ \rightarrow$ 排序寫回 $\rightarrow\ [6,7,9,11,13]$
  組中位索引 $1+2g=5$，值 $9$
- 此時整段：$[14,6,18,7,20,9,22,11,25,13]$
- 所有組中位數切片：$A[p+2g..p+3g-1]=A[4..5]=[20,9]$（長度 $g=2$）
2) 在「組中位數切片」上取中位
- 呼叫 SELECT(A, 4, 5, ⌈g/2⌉=1)
- 得 $x=9$（median-of-medians）
3) 以 $x$ 分割整段
- PARTITION-AROUND(A, 0, 9, x=9)，把陣列切為「$\le 9$ | $\ge 9$」，並將 $x$ 放至正確位置 $q$
- 這裡 $\le 9$ 元素為 ${6,7,9}$，故 $k=q-p+1=3$
- 一種可能結果：$[6,7,9,14,20,18,22,11,25,13]$ 且 $q=2$
4) 決定遞迴方向（欲找第 $i$ 小）
- $i=3$：命中，答案 $9$
- $i<3$：往左子陣列 $A[0..1]$
- $i>3$：往右子陣列 $A[3..9]$，改找第 $i-3$ 小