對於給定的n個元素的數組a[0 : n - 1]，要求從中找出第k小的元素。當a[0 : n - 1]被排序時，該元素就是a[k - 1]。假設n=8，每個元素有兩個域k e y和I D，其中k e y是一個整數，I D是一個字符。假設這8個元素為[( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序後得到數組[( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h)]。如果k=1，返回I D為g 的元素；如果k=8，返回I D為h 的元素；如果k=6，返回是I D為f 的元素；如果k=2，返回I D為d 的元素。實際上，對最後一種情況，所得到的結果可能不唯一，因為排序過程中既可能將I D為d 的元素排在a[1]，也可能將I D為b 的元素排在a[1]，原因是它們具有相同大小的k e y，因而兩個元素中的任何一個都有可能被返回。但是無論如何，如果一個元素在k=2時被返回，另一個就必須在k=3時被返回。
選擇問題的一個應用就是尋找中值元素，此時k=[n / 2]。中值是一個很有用的統計量，例如中間工資，中間年齡，中間重量。其他k值也是有用的。例如，通過尋找第n / 4 , n / 2和3 n / 4這三個元素,可將人口劃分為4份。
選擇問題可在O( n l o g n )時間內解決，方法是首先對這n個元素進行排序（如使用堆排序式或歸並排序），然後取出a[k - 1]中的元素。若使用快速排序（如圖1 4 - 11所示），可以獲得更好的平均性能，盡管該算法有一個比較差的漸近復雜性O( n2 )。
可以通過修寫程序1 4 - 6來解決選擇問題。如果在執行兩個w h i l e循環後支點元素a[l]被交換到a[j] ,那麼a[l]是a[l : j]中的第j - l + 1個元素。如果要尋找的第k個元素在a[l : r]中，並且j - l + 1等於k，則答案就是a[l]；如果j - l + 1 <k，那麼尋找的元素是r i g h t中的第k - j + l - 1個元素，否則要尋找的元素是left中的第k個元素。因此，只需進行0次或1次遞歸調用。新代碼見程序1 4 - 7。S e l e c t中的遞歸調用可用f o r或w h i l e循環來替代（練習2 5）。
程序14-7 尋找第k個元素
template
T Select(T a[], int n, int k)
{// 返回a[0 : n - 1]中第k小的元素
// 假定a[n]是一個偽最大元素
if(k <1 || k >n) throw OutOfBounds();
return select(a, 0, n-1, k);
}
template
T select(T a[], int l, int r, int k)
{// 在a[l : r]中選擇第k小的元素
if(l >=r) return a[l];
int i=l, // 從左至右的游標
j=r + 1; // 從右到左的游標
T pivot=a[l];
// 把左側>=pivot的元素與右側<=pivot 的元素進行交換
while(true) {
do {// 在左側尋找>=pivot 的元素
i=i + 1;
} while(a[i] <pivot);
do {// 在右側尋找<=pivot 的元素
j=j - 1;
} while(a[j] >pivot);
if(i >=j) break; // 未發現交換對象
Swap(a[i], a[j]);
}
if(j - l + 1==k) return pivot;
// 設置p i v o t
a[l]=a[j];
a[j]=pivot;
// 對一個段進行遞歸調用
if(j - l + 1 <k)
return select(a, j+1, r, k-j+l-1);
else return select(a, l, j-1, k);
}
程序1 4 - 7在最壞情況下的復雜性是( n2 )，此時left 總是為空，而且第k個元素總是位於r i g h t.
如果假定n是2的冪，則可以取消公式（2 - 1 0）中的向下取整操作符。通過使用迭代方法，可以得到t(n)=(n)。若仔細地選擇支點元素，則最壞情況下的時間開銷也可以變成(n)。一種選擇支點元素的方法是使用“中間的中間（ m e d i a n - o f - m e d i a n）”規則，該規則首先將數組a中的n個元素分成n/r 組，r 為某一整常數，除了最後一組外，每組都有r個元素。然後通過在每組中對r個元素進行排序來尋找每組中位於中間位置的元素。最後根據所得到的n/r個中間元素，遞歸使用選擇算法，求得所需要的支點元素。
例2-6[中間的中間] 考察如下情形：r=5, n=27, 並且a=[2，6，8，1，4，1 0，2 0，6，2 2，11，9，8，4，3，7，8，1 6，11，1 0，8，2，1 4，1 5，1，1 2，5，4]。這2 7個元素可以被分為6組[2 , 6 , 8 , 1 , 4]，[1 0 , 2 0 , 6 , 2 2 , 11]，[9 , 8 , 4 , 3 , 7]，[8 , 1 6 , 11 , 1 0 , 8]，[2 , 1 4 , 1 5 , 1 , 1 2]和[5 , 4]，每組的中間元素分別為4 , 11 , 7 , 1 0 , 1 2和4。[4 , 11 , 7 , 1 0 , 1 2 , 4]的中間元素為7。這個中間元素7被取為支點元素。由此可以得到l e ft=[2 , 6 , 1 , 4 , 6 , 4 , 3 , 2 , 1 , 5 , 4]，m i d d l e=[7] ,r i g h t=[8 , 1 0 , 2 0 , 2 2 , 11 , 9 , 8 , 8 , 1 6 , 11 , 1 0 , 8 , 1 4 , 1 5 , 1 2]。
如果要尋找第k個元素且k<1 2，則僅僅需要在l e f t中尋找；如果k=1 2，則要找的元素就是支點元素；如果k>1 2，則需要檢查r i g h t中的1 5個元素。在最後一種情況下，需在r i g h t中尋找第(k- 1 2 )個元素。
定理2-2 當按“中間的中間”規則選取支點元素時，以下結論為真：
1) 若r=9, 那麼當n≥9 0時，有m a x { |l e f e|, |r i g h t| }≤7n / 8。
2) 若r=5，且a中所有元素都不同，那麼當n≥2 4時，有max{| left |, | right | }≤3n/ 4。
證明這個定理的證明留作練習2 3。
根據定理2 - 2和程序1 4 - 7可知，如果采用“中間的中間”規則並取r=9，則用於尋找第k個元素的時間t(n)可按如下遞歸公式來計算：
在上述遞歸公式中，假設當n＜9 0時使用復雜性為nl o gn的求解算法，當n≥9 0時，采用“中間的中間”規則進行分而治之求解。利用歸納法可以證明，當n≥1時有t(n)≤7 2cn(練習2 4 )。
當元素互不相同時，可以使用r=5來得到線性時間性能。
