选择问题的要求是找出含有 N 个元素的表 S 中的第 k 个最小的元素。
基本的算法是简单的递归策略。设 N 大于截止点(cutoff point)，在截止点后元素将进行简单的排序，v 是选出的一个元素，叫做枢纽元(pivot)。其余的元素被放在两个集合 和
中。
含有那些不大于 v 的元素，而
则包含那些不小于 v 的元素。
为了得到一个线性算法，必须保证子问题只是原问题的一部分，而不仅仅只是比原问题少几个元素。这里要解决问题就是如何花费更少的时间来寻找枢纽元。
为得到一个好的最坏情形，关键想法是再用一个间接层。不是从随机元素的样本中找出中项，而是从中项的样本中找出中项。
基本的枢纽元选择算法如下：
- 把 N 个元素分成 「N/5」组，5 个元素一组，忽略(最多 4 个)剩余的元素。
- 找出每组的中项，得到「N/5」个中项的表 M。
- 求出 M 的中项，将其作为枢纽元 v 返回。
上面给出的枢纽元选择法，有一个专业的术语，叫做“五分化中项的中项”。“五分化中项的中项”保证每个递归子问题的大小最多是原问题的大约 70%。对于整个选择算法，枢纽元可以足够快的算出，以确保 的运行时间。
定理：使用“五分化中项的中项”的快速选择算法的运行时间为 。
降低比较的平均次数
分治算法还可以用来降低算法预计所需要的比较次数。
设有 N 个数的集合 S 并且要寻找其中第 k 个最小的数 X。我们选择 S 的子集 S‘，令 δ 是某个数，使得计算过程所用的平均比较次数最小化。
找出 S’ 中第 () 个和第
个最小的元素，几乎可以肯定 S 中的第 k 个元素将落在
和
之间，此时，问题变成了 2δ 个元素的选择问题。
经过分析，会发现，若 和
，则期望的比较次数为
，除低次项外它是最优的。（如果 k>N/2，那么我们可以考虑查找第(N-k)个最大元素的对称问题。）
最后一项代表进行两次选择以确定 和
的代价。假设采用合理聪明的策略，则划分的平均代价等于 N 加上
在 S 中的期望阶(expected rank)，即
。如果第 k 个元素在 S‘ 中出现，那么代价就是 O(N)。然而，s 和 δ 已经被选取以保证这种情况以非常低的概率 o(1/N) 发生，因此该可能性的期望代价是 o(1)，当它的 N 越来越大时趋向于 0。
这个分析指出，找出中项平均大约需要 1.5N 次比较。当然，该算法为计算 s 需要浮点运算，这在一些机器上可能使该算法减慢速度。不过即使是这样，若能正确实现，则该算法完全能够比得上快速选择实现方法。
