一个n个元素组成的集合中，第K个顺序统计量（Order Statistic）指的是该集合中第K小的元素，我们这里要讨论的是如何在线性时间（linear time）里找出一个数组的第K个顺序统计量。该问题的算法对于C++程序员来说有一定的借鉴价值。具体如下：

一、问题描述：

问题：给定一个含有n个元素的无序数组，找出第k小的元素。

k = 1 ：最小值
k = n ：最大值
k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ ：中位数

找最大值或最小值很简单，只需要遍历一次数组并记录下最大值或最小值就可以了。我们在这里要解决的问题是一般性的选择问题。

一种原始的解决方案是，用堆排序或归并排序将输入数据进行排序，然后返回第k个元素。这样在Θ(nlgn)时间内一定可以解决。但是我们希望有更好的方案，最好是线性时间。

二、期望线性时间的解决方案：

为了在线性时间内解决这个选择问题，我们使用一个随机的分治算法，即RANDOMIZED-SELECT算法。此算法是使用随机化的快速排序中的随机划分子程序，对输入数组进行随机划分操作，然后判断第k小元素在划分后的哪个区域，对所在区域进行递归划分，最后找到第k小元素。

伪代码如下：

RANDOMIZED-SELECT(A,p,q,i) // i-th smallest in A[p..q] 
  if p = q 
    then return A[p] 
  r = RANDOMIZED-PARTITION(A, p, q) 
  k = r-p+1  // A[r] is k-th smallest 
  if i=k 
    then return A[r] 
  if i