Quickselect

在計算機科學中，**快速選擇**（英語：Quickselect）是一種從無序列表找到第 k 小元素的選擇算法。它從原理上來說與快速排序有關。與快速排序一樣都由托尼・霍爾提出的，因而也被稱為**霍爾選擇算法**。 同樣地，它在實際應用是一種高效的算法，具有很好的平均時間複雜度，然而最壞時間複雜度則不理想。快速選擇及其變種是實際應用中最常使用的高效選擇算法。

快速選擇的總體思路與快速排序一致，選擇一個元素作為基準來對元素進行分區，將小於和大於基準的元素分在基準左邊和右邊的兩個區域。不同的是，快速選擇並不遞歸訪問雙邊，而是只遞歸進入一邊的元素中繼續尋找。這降低了平均時間複雜度，從 O (_n_ log _n_) 至 O (_n_)，不過最壞情況仍然是 O (_n_2)。

與快速排序一樣，快速選擇一般是以原地算法的方式實現，除了選出第 k 小的元素，數據也得到了部分地排序。

## 算法

快速排序中，有一個子過程稱為分區，可以在線性時間裡將一個列表分為兩部分（`left` 和 `right`），分別是小於基準和大於等於基準的元素。下面是以 `list[pivotIndex]` 進行分區的偽代碼：

```
 **function** partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  _// Move pivot to end_
     storeIndex := left
     **for** i **from** left **to** right-1
         **if** list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  _// Move pivot to its final place_
     **return** storeIndex
```

在快速排序中，我們遞歸地對兩個分支進行排序，導致最佳時間複雜度為 O (_n_ log _n_)。然而，在快速選擇中，雖然大部分元素仍是亂序的，但是基準元素已經在最終排序好的位置上，所以我們知道想找的元素在哪個分區中。 因此，一個遞歸循環分支就能幫助我們定位想找的元素，從而得到快速選擇的算法：

```
  _// Returns the k-th smallest element of list within left..right inclusive_
  _// (i.e. left <= k <= right)._
  _// The search space within the array is changing for each round - but the list_
  _// is still the same size. Thus, k does not need to be updated with each round._
  **function** select(list, left, right, k)
     **if** left = right        _// If the list contains only one element,_
         **return** list[left]  _// return that element_
     pivotIndex  := ...     _// select a pivotIndex between left and right,_
                            _// e.g.,_ left + floor(rand() % (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     _// The pivot is in its final sorted position_
     **if** k = pivotIndex
         **return** list[k]
     **else if** k < pivotIndex
         **return** select(list, left, pivotIndex - 1, k)
     **else**
         **return** select(list, pivotIndex + 1, right, k)
```

注意到與快速排序的相似之處：就像基於尋找最小值的選擇算法是部分選擇排序，這可以認為是部分快速排序，只進行 O (_n_ log _n_) 而不是 O (_n_) 次分區。這個簡單的過程具有預期的線性時間複雜度，並且如快速排序一樣有相當良好的實際表現。 這也是一個原地算法，只需要棧內常數級的內存，或者可以用循環來去掉尾遞歸：

```
 **function** select(list, left, right, k)
     **loop**
         **if** left = right
             **return** list[left]
         pivotIndex := ...     _// select pivotIndex between left and right_
         pivotIndex := partition(list, left, right, pivotIndex)
         **if** k = pivotIndex
             **return** list[k]
         **else if** k < pivotIndex
             right := pivotIndex - 1
         **else**
             left := pivotIndex + 1
```

## 時間複雜度

與快速排序類似，快速選擇算法在平均狀況下有著不錯的表現，但是對於基準值的選擇十分敏感。如果基準值選擇上佳，搜索範圍每次能夠指數級減少，這樣一來所耗時間是線性的 (即 O (n))。但如果基準值選擇非常不好，使得每次只能將搜索範圍減少一個元素，則最糟的總體時間複雜度是平方級的 (O (_n_2))：例如對一個升序排列的數組搜索其最大值，而每次都選擇第一個元素作為基準值。

## 算法變體

最簡單的快速排序變化是每次隨機選擇基準值，這樣可以達到近乎線性的複雜度。更為確定的做法是採用「取三者中位數」的基準值選擇策略，這樣對已部分排序的數據依然能夠達到線性複雜度。但是，特定人為設置的數組在此方法下仍然會導致最差時間複雜度，如大衛・穆塞爾所描述的「取三者中位數殺手」數列，這成為他發表反省式選擇算法的動機。

利用中位數的中位數算法，可以在最壞情形下依然保證線性時間複雜度。但是這一方法中的基準值計算十分複雜，實際應用中並不常見。改進方法是在快速選擇算法的基礎上，使用「中位數的中位數」算法處理極端特例，這樣可以保證平均狀態與最差情形下的時間複雜度都是線性的，這也是反省式選擇算法的做法。

精確計算下，隨機選擇基準值策略最差會導致 $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ 複雜度。採用 Floyd–Rivest 算法可以使這一常數進一步減少，在最壞情形下達到 $1.5n+O(n^{1/2})$ 。

## 參考文獻