快速選擇
| 快速選擇 | |
|---|---|
 快速選擇算法的動畫演示：選擇第22小的元素。（注意：這和條目中的算法不完全相同） | |
| 概況 | |
| 類別 | 選擇算法 |
| 資料結構 | 數組 |
| 複雜度 | |
| 平均時間複雜度 | O(n) |
| 最壞時間複雜度 | О(n2) |
| 最優時間複雜度 | О(n) |
| 空間複雜度 | O(1) |
| 相關變量的定義 | |
在計算機科學中，快速選擇（英語：Quickselect）是一種從無序列表找到第k小元素的選擇算法。它從原理上來說與快速排序有關。與快速排序一樣都由托尼·霍爾提出的，因而也被稱為霍爾選擇算法。[1] 同樣地，它在實際應用是一種高效的算法，具有很好的平均時間複雜度，然而最壞時間複雜度則不理想。快速選擇及其變種是實際應用中最常使用的高效選擇算法。
快速選擇的總體思路與快速排序一致，選擇一個元素作為基準來對元素進行分區，將小於和大於基準的元素分在基準左邊和右邊的兩個區域。不同的是，快速選擇並不遞歸訪問雙邊，而是只遞歸進入一邊的元素中繼續尋找。這降低了平均時間複雜度，從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))：例如對一個升序排列的數組搜索其最大值，而每次都選擇第一個元素作為基準值。
算法變體
[編輯]最簡單的快速排序變化是每次隨機選擇基準值，這樣可以達到近乎線性的複雜度。更為確定的做法是採用「取三者中位數」[2]的基準值選擇策略，這樣對已部分排序的數據依然能夠達到線性複雜度。但是，特定人為設置的數組在此方法下仍然會導致最差時間複雜度，如大衛·穆塞爾所描述的「取三者中位數殺手」數列，這成為他發表反省式選擇算法的動機。
利用中位數的中位數算法，可以在最壞情形下依然保證線性時間複雜度。但是這一方法中的基準值計算十分複雜，實際應用中並不常見。改進方法是在快速選擇算法的基礎上，使用「中位數的中位數」算法處理極端特例，這樣可以保證平均狀態與最差情形下的時間複雜度都是線性的，這也是反省式選擇算法的做法。
精確計算下，隨機選擇基準值策略最差會導致複雜度。採用Floyd–Rivest算法可以使這一常數進一步減少，在最壞情形下達到 。
