選擇問題的要求是找出含有 N 個元素的表 S 中的第 k 個最小的元素。
基本的算法是簡單的遞歸策略。設 N 大于截止點(cutoff point)，在截止點后元素將進行簡單的排序，v 是選出的一個元素，叫做樞紐元(pivot)。其余的元素被放在兩個集合 和
中。
含有那些不大于 v 的元素，而
則包含那些不小于 v 的元素。
為了得到一個線性算法，必須保證子問題只是原問題的一部分，而不僅僅只是比原問題少幾個元素。這里要解決問題就是如何花費更少的時間來尋找樞紐元。
為得到一個好的最壞情形，關鍵想法是再用一個間接層。不是從隨機元素的樣本中找出中項，而是從中項的樣本中找出中項。
基本的樞紐元選擇算法如下：
- 把 N 個元素分成 「N/5」組，5 個元素一組，忽略(最多 4 個)剩余的元素。
- 找出每組的中項，得到「N/5」個中項的表 M。
- 求出 M 的中項，將其作為樞紐元 v 返回。
上面給出的樞紐元選擇法，有一個專業(yè)的術語，叫做“五分化中項的中項”?！拔宸只许椀闹许棥北ＷC每個遞歸子問題的大小最多是原問題的大約 70%。對于整個選擇算法，樞紐元可以足夠快的算出，以確保 的運行時間。
定理：使用“五分化中項的中項”的快速選擇算法的運行時間為 。
降低比較的平均次數(shù)
分治算法還可以用來降低算法預計所需要的比較次數(shù)。
設有 N 個數(shù)的集合 S 并且要尋找其中第 k 個最小的數(shù) X。我們選擇 S 的子集 S‘，令 δ 是某個數(shù)，使得計算過程所用的平均比較次數(shù)最小化。
找出 S’ 中第 () 個和第
個最小的元素，幾乎可以肯定 S 中的第 k 個元素將落在
和
之間，此時，問題變成了 2δ 個元素的選擇問題。
經過分析，會發(fā)現(xiàn)，若 和
，則期望的比較次數(shù)為
，除低次項外它是最優(yōu)的。（如果 k>N/2，那么我們可以考慮查找第(N-k)個最大元素的對稱問題。）
最后一項代表進行兩次選擇以確定 和
的代價。假設采用合理聰明的策略，則劃分的平均代價等于 N 加上
在 S 中的期望階(expected rank)，即
。如果第 k 個元素在 S‘ 中出現(xiàn)，那么代價就是 O(N)。然而，s 和 δ 已經被選取以保證這種情況以非常低的概率 o(1/N) 發(fā)生，因此該可能性的期望代價是 o(1)，當它的 N 越來越大時趨向于 0。
這個分析指出，找出中項平均大約需要 1.5N 次比較。當然，該算法為計算 s 需要浮點運算，這在一些機器上可能使該算法減慢速度。不過即使是這樣，若能正確實現(xiàn)，則該算法完全能夠比得上快速選擇實現(xiàn)方法。
