選擇算法

在計算機科學中，選擇算法是一種在列表或數組中找到第k個最小數字的算法；這樣的數字被稱為第k個順序統計量。該算法尋找的對象主要有三種：最小、最大和中位數。已知存在O(n)（最壞情況下為線性時間）的選擇算法，還有對於結構化數據可能有次線性的表現的算法；在極端的情況下，對於已排序數據是O(1)。選擇是一些更複雜問題的子問題，如最近鄰和最短路徑問題。 許多選擇算法是由排序算法推廣而來，反之，一些排序算法可由反覆應用選擇算法推導出來。

最簡單的選擇算法是通過遍歷列表找到最小（或最大）的元素，在此過程中跟蹤當前的最小（或最大）值。這種算法與選擇排序有關。相反地，最困難的選擇算法是尋找中位數，這必然需要n/2的空間。 事實上，一個專門的中位選擇算法可用來構造一個一般選擇算法，例如中位數的中位數。已知最好的選擇算法是快速選擇（quickselect），它與快速排序有關。和快速排序類似，它有漸進最佳的複雜度，但是最壞情況的複雜度較差。不過這可以通過調整基準（pivot）的選擇來優化。

通過排序選擇

通過對列表或數組的排序，然後選擇所需的元素，選擇算法可以規約為排序算法。這種方法對於選擇單個元素是低效的，但需要從數組中做出很多選擇時是高效的。在這種情況下，僅僅需要一個起初一個代價昂貴的排序，緊接著就是各種便宜的選擇操作了 – 對於數組而言是 O(1)。儘管對於鍊表而言，即使排序後，選擇操作也需要 O(n)，這是由於缺乏隨機訪問造成的。通常的，排序需要耗費 O(n log n) 的時間，其中 n 是列表的長度，儘管對於非比較算法而言可能更低一些，如基數排序和計數排序。

相比將整個列表或數組進行排序，還可以用偏排序來選擇第 k 小或第 k 大的元素。第 k 小的（第 k 大的) 也就是偏排序後列表中最大的 (最小的) 那個 – 這在數組中會耗費 O(1) 來訪問，在鍊表中會耗費 O(k)。

參見

• 序優化

外部連結

• "Lecture notes for January 25, 1996: Selection and order statistics （頁面存檔備份，存於網際網路檔案館）", ICS 161: Design and Analysis of Algorithms, David Eppstein