快速選擇

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

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

與快速排序一樣，快速選擇一般是以原地算法的方式實現，除了選出第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(n2))：例如對一個升序排列的陣列搜索其最大值，而每次都選擇第一個元素作為基準值。

## 演算法變體

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

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

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