在一个由元素组成的集合里，第i个顺序统计量（orderstatistic）是该集合第i小的元素。例如，最小值是第1个顺序统计量(i=1)，最大值是第n个顺序统计量(i=n)。一个中位数（median）是它所在集合的“中点元素”。当n为奇数时，中位数是唯一的，i=(n+1)/2；当n为偶数时，中位数有两个，一个是i=floor((n+1)/2)（下中位数），另一个是i=ceiling((n+1)/2)（上中位数）。在不考虑n的奇偶性的情况下，中位数总是出现在i=floor((n+1)/2)处和i=ceiling((n+1)/2)处。
最小值和最大值
在一个有n个元素的集合里，要找到最小元素，可以用下面的代码：
如果要同时找出最大值和最小值，我们很容易想到让每一个元素分别和min和max比较，这样每个元素要进行2次比较，而总的比较数就为2*n-2。事实上只需3*floor(n/2)次比较就可以同时找到最小值和最大值。我们并不让每个元素同时与min和max比较，而是取两个元素先比较，较大的元素与max比较，而较小的元素与min比较，这样每两个元素要做3次比较，总的比较次数最多为3*floor(n/2)。
如果我们不选最大值或最小值，而是选一个第i小的值。我们可以用一种分治算法——RAMDOMIZED_SELECT，它以快速排序为模型：把数组随机划分为两部分，A[p...q-1]的元素比A[q]小，A[q+1...r]的元素比A[q]大。与快速排序不同，如果i=q，则A[q]就是要找的第i小的元素，返回这个值；如果iq，则说明第i小的元素在A[q+1...r]里。
下面是在A[p...r]中找到第i小元素的代码：
设指示器随机变量X_k=I{子数组A[p...q]中恰有k个元素}这样，元素数量为n的数组在每次划分时，就会被划分为1...k-1,k,k+1...n三部分。下次递归时，就可以作用在1...k-1（共k-1个元素）区间或k+1...n（共n-k个元素）区间上。考虑X_k所有可能的取值，则可以得到递归式：T(n)≤∑X_k*T(max(k-1,n-k))+O(n)=∑(X_k*T(max(k-1,n-k))+O(n))
由于X_k为1的概率为1/n，取期望值，得到：E(T(n))≤E[∑(X_k*T(max(k-1,n-k))+O(n))]=∑E[(X_k*T(max(k-1,n-k))]+O(n)=∑E[X_k]*E[T(max(k-1,n-k))]+O(n)（X_k与T(max(k-1,n-k))独立）=∑1/n*E[T(max(k-1,n-k))]+O(n)
考虑max(k-1,n-k)，如果k>ceiling(n/2)，其值为k-1；若k≤ceiling(n/2)，其值为n-k。所以∑T(max(k-1,n-k))≤2*∑T(k)，于是有：E(T(n))≤2/n*∑E[T(k)]+O(n)
相比于上面的随机选择，我们有另一种类似的算法，它在最坏情况下也能达到O(n)。它也是基于数组的划分操作，而且利用特殊的手段保证每次划分两边的子数组都比较平衡。
首先我们需要稍微修改一下PARTITION算法（不是RANDOMIZED_PARTITION)，它接收一个数组和一个值x，并把它划分为小于x和大于x的两部分（x为A中某个元素的值）：
在修改划分算法后，我们通过以下步骤来实现在n个元素的数组中找第i小元素的SELECT：１、把数组A分成ceiling(n/5)个组，除最后一组外，每组都有5个元素，最后一组有nmod5个元素；２、对每组（的五个元素）用插入法进行排序，然后选出该组的中位数，即排好序的第三个元素；３、对于步骤2中得到的所有的中位数，通过递归调用SELECT来找到它们的（下）中位数x，（也就是找到第2步得到的所有中位数中第floor(ceiling(n/5)/2)小个元素）；４、利用修改后的划分算法把元素分成小于x和大于x的两个子数组。如果设k为划分低区的元素个数加一，则x就是A中第k小的元素；５、如果i=k，那我们就返回x，它便是我们要找的值。如果ik，我们就在划分高区递归调用SELECT找第i-k小的数。
下面是伪代码：
综上所述，可以得到递归式：T(n)≤T(floor(n/5))+T(7*n/10+6)+O(n)
用代换法来解上面的递归式，设c,a为正常数得：T(n)≤c*(floor(n/5))+c*(7*n/10+6)+a*n≤c*(n/5)+c*(7*n/10+6)+a*n=9*c*n/10+7*c+a*n=c*n+(-c*n/10+7*c+a*n)