跳至主要内容

Quickselect

預備知識
  • Sorting（尤其是 Quick Sort 的 Partition 概念）

Quickselect 是一種用來在未排序的陣列中，尋找「第 k 小」或「第 k 大」元素的超高效演算法，這類題目時常會用 Heap 來解，但是 Quickselect 的時間會更快。

與 Quick Sort 使用一樣的核心邏輯，但 Quickselect 的速度比排序還要快上許多。

當我們要找第 k 小的數字時，一般的直覺是「把整個陣列排好序，再直接用索引（Index）撈出來」。但排序需要花比較多的時間 O(n log n)。

而 Quickselect 不需要把整個陣列排好，所以處理速度非常快速。

白話理解

想像要在一疊沒排序的考卷裡找出「第 3 高分」，不需要把所有考卷從高到低排好序才能知道答案。只要每次隨便挑一張當標準，把比它高分和比它低分的分成兩堆，確認第 3 名落在哪一堆之後，直接丟掉另一堆繼續找，完全不用管被丟掉那一堆內部誰高誰低。

步驟​

題目：要找一堆數字中排序第 k 小的數

  1. 挑選基準點（Pivot）
  2. Partition
  3. Selection（前兩步都和 Quick Sort 相同，這一步則不同）

實作​

Partition​

和 Quick Sort 相同，這邊不贅述。

def partition(arr, start, end):
    pivot = arr[end]
    i = start

    for j in range(start, end):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]  # 交換位置
            i += 1

    # 將基準值換到正確的位置
    arr[i], arr[end] = arr[end], arr[i]
    return i

Selection​

前面的處理方式都和 Quick Sort 相同，到這一步則不同：

  • 如果 p 剛好就是我們要找的 k，直接回傳答案
  • 如果 p 比 k 大，代表第 k 小的數一定在左半邊。就只去左半邊繼續找，直接省去右半邊
  • 如果 p 比 k 小，代表答案一定在右半邊。就只去右半邊繼續找，直接省去左半邊
def quick_select(arr, k, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    pivot_idx = partition(arr, left, right)
    if pivot_idx == k:
        return arr[pivot_idx]
    if pivot_idx > k:
        return quick_select(arr, k, left, pivot_idx - 1)
    else:
        return quick_select(arr, k, pivot_idx + 1, right)

如果是要求回傳前 k 個元素，則將答案改成擷取前 k 個元素。

這前 k 個元素不見得是排序好的，不過通常題目不會要求排序正確。

def quick_select(arr, k, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    pivot_idx = partition(arr, left, right)
    if pivot_idx == k:
        return arr[:k]
    if pivot_idx > k:
        return quick_select(arr, k, left, pivot_idx - 1)
    else:
        return quick_select(arr, k, pivot_idx + 1, right)

逐步拆解：在 [9, 2, 7, 4, 1] 中找第 3 小的數（k = 2，從 0 開始算）​

  1. 第一輪 Partition，以最後一個元素 1 當 Pivot：
    • 掃描過程中沒有任何數字小於等於 1（除了它自己），所以 Pivot 直接換到最前面。
    • Partition 後陣列變成 [1, 2, 7, 4, 9]，Pivot 的最終位置 pivotIdx = 0。
    • 比較 pivotIdx (0) 與 k (2)：pivotIdx < k，代表答案在右半邊，繼續只在 [2, 7, 4, 9]（index 1 ~ 4）裡尋找。
  2. 第二輪 Partition，以最後一個元素 9 當 Pivot：
    • 2、7、4 全部都小於等於 9，所以整個範圍原封不動，Pivot 換到最後。
    • Partition 後陣列不變，Pivot 的最終位置 pivotIdx = 4。
    • 比較 pivotIdx (4) 與 k (2)：pivotIdx > k，代表答案在左半邊，繼續只在 [2, 7, 4]（index 1 ~ 3）裡尋找。
  3. 第三輪 Partition，以最後一個元素 4 當 Pivot：
    • 2 小於等於 4，換到左邊；7 大於 4，維持原位。
    • Partition 後陣列變成 [1, 2, 4, 7, 9]，Pivot 的最終位置 pivotIdx = 2。
    • 比較 pivotIdx (2) 與 k (2)：剛好相等！直接回傳 arr[2]，也就是 4。

整個過程完全不需要把 7 和 9 排序，因為一旦確定答案不在那個範圍內，就直接捨棄，這正是 Quickselect 比完整排序快的原因。

適用情況​

  • 找第 k 大 / 第 k 小的元素：例如 Leetcode: Kth Largest Element in an Array。
  • 找中位數（Median）：中位數其實就是「第 n/2 小的數」，可以直接套用 Quickselect。
  • 只需要「前 k 大 / 前 k 小」，但不要求這些結果本身是排序好的：例如篩選出成績前 10 名的學生名單，但不需要知道這 10 人之間誰名次更前面。

如果題目需要「持續動態地」找極值（例如資料不斷新增），Heap 會是更適合的選擇；但如果資料是「一次給定、只需要找一次答案」，Quickselect 平均會更快。

常見誤區​

  • 誤以為一定要把左右兩邊都遞迴下去：Quickselect 只需要往「答案所在的那一半」繼續遞迴，另一半可以直接丟棄，這也是它比 Quick Sort 快的關鍵，別誤寫成跟 Quick Sort 一樣兩邊都遞迴。
  • k 的定義搞混：要確認題目要求的「第 k 小」是從 0 開始算（index）還是從 1 開始算（第幾名），下手前先確認清楚，以免答案差一位。
  • 忽略最壞情況：如同 Quick Sort，如果每次都選到最差的 Pivot，時間複雜度會退化成 O(n^2)，實務上可透過「隨機選 Pivot」降低踩到最壞情況的機率。

複雜度​

  • 平均時間複雜度：O(n)
    • 第一次掃描 n 個元素，第二次剩 n/2，第三次剩 n/4...加起來的總和無限接近 2n，所以是常數級別的 線性時間 O(n)。這比先排序再找（O(n log n)）快非常多！
  • 最壞時間複雜度：O(n^2)
    • 如果每次選 Pivot 都倒楣選到最大或最小的數，導致每次只能刪掉 1 個元素（例如陣列本來就排好序，又一直選最後一個當 Pivot），就會退化成 O(n^2)。

另外附上與 Heap 的比較，當處理「找未排序陣列中第 (k) 大元素」的問題時：

演算法平均時間複雜度最壞時間複雜度空間複雜度
QuickselectO(n)O(n^2)O(1) (迭代版) / O(log n) (遞迴版)
Min Heap (維持大小為 k 的小頂堆)O(n log k)O(n log k)O(k)
Max Heap (對 n 個元素建大頂堆)O(n + k log n)O(n + k log n)O(1) 或 O(n)
最後於 更新