跳至主要内容

Quickselect

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

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

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

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

步驟​

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

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

實作​

Partition​

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

function partition(arr, start, end) {
    let pivot = arr[end];
    let i = start;
    
    for (let j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // 交換位置
            i++;
        }
    }
    
    // 將基準值換到正確的位置
    [arr[i], arr[end]] = [arr[end], arr[i]];
    return i;
}

Selection​

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

  • 如果 p 剛好就是我們要找的 k，直接回傳答案
  • 如果 p 比 k 大，代表第 k 小的數一定在左半邊。就只去左半邊繼續找，直接省去右半邊
  • 如果 p 比 k 小，代表答案一定在右半邊。就只去右半邊繼續找，直接省去左半邊
function quickSelect(arr, k, left = 0, right = arr.length - 1) {
  const pivotIdx = pivotHelper(arr, left, right);
  if (pivotIdx === k) return arr[pivotIdx];
  if (pivotIdx > k) return quickSelect(arr, k, left, pivotIdx - 1);
  else return quickSelect(arr, k, pivotIdx + 1, right);
}

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

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

function quickSelect(arr, k, left = 0, right = arr.length - 1) {
  const pivotIdx = pivotHelper(arr, left, right);
  if (pivotIdx === k) return arr.slice(0, k);
  if (pivotIdx > k) return quickSelect(arr, k, left, pivotIdx - 1);
  else return quickSelect(arr, k, pivotIdx + 1, right);
}

複雜度​

  • 平均時間複雜度：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)
最後於 更新