这称为找到第 k 阶统计量 。有一个非常简单的随机算法（称为 quickselect
）采用O(n)平均时间、O(n^2)最坏情况时间，还有一个非常复杂的非随机算法（称为 introselect
）采用O(n)最坏情况时间。维基百科上有一些信息，但不是很好。

您需要的一切都在 这些 powerpoint
幻灯片中。只是为了提取O(n)最坏情况算法的基本算法（introselect）：

Select(A,n,i):
    Divide input into 鈱坣/5鈱� groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group鈥檚 median.
    pivot = Select(medians, 鈱坣/5鈱�, 鈱坣/10鈱�)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Cormen 等人的《算法简介》一书中也非常详细地介绍了这一点。