概念

顺序统计量

在一个由ｎ个元素组成的集合中，第ｉ个顺序统计量(order statistic)是该集合中第ｉ小的元素。例如，在一个元素集合中，最小值是第1个顺序统计量(i=1), 最大值是第ｎ个顺序统计量。

选择问题

从一个由ｎ个互异的元素组成的集合中，选择第ｉ个顺序统计量被称为选择问题。

思想

解决选择问题，很自然想到先对输入进行一次排序，然后输出第i个元素即可，这种方法时间复杂度最好可以做到O(nlogn)。是否可以优化呢？问题本身是要求第ｉ个元素，但是我们这种解法却对其排序，显然我们做多了，其中存在冗余操作。回想快速排序过程使用partition过程，可以将一个序列分为小于主元、主元、大于主元部分，并且返回一个索引ｉ，下标为ｉ的元素即为第i+1（考虑数组小标从０开始）个顺序统计量。

伪代码

// 在A[p...r]内选择第ｉ个顺序统计量
Select(A,p,r,i)
  if p==r
    return A[p]
  // 执行partition过程　
  q = partition(A, p, r)
  // k表示ｐａｒｔｉｔｉｏｎ后左边元素个数，即A[q]是第ｋ个顺序统计量
  k = q-p+1
  if k == i
    // partition返回的索引即为需要顺序统计量
    return A[q]
  else if i<k
　　// 在左半边继续寻找
    return Select(A, p, q-1, i)
  else
　  //在右半边寻找，此时需要把左边的元素计数去除
    return Select(A, q+1, r, i-k)

源码

talk is chip, show me your code.

int __partition(int arr[], int L, int R)
{
    // (L, i-1] <= v <= [i,j)
    int i=L+1, j =L+1;
    int v=arr[L];
    for(;j<=R;j++){
        if (arr[j]<v){
            swap(arr[j], arr[i++]);
        }
    }
    swap(arr[L], arr[i-1]);
    return i-1;
}
// 寻找arr[L...R]的第ｉｎｄｅｘ顺序统计量
int __select(int arr[], int L, int R, int index)
{
    if(L == R){
        return arr[L];
    }
    int i = __partition(arr, L, R);
    int k = i-L+1;
    if  (k==index){
        return arr[i];
    }else if(index<k){
        return __select(arr, L, i-1, index);
    }else{
        return __select(arr, i+1, R, index-(i-L+1));
    }
}
int select(int arr[], int size, int index)
{
    return __select(arr, 0, size-1, index);
}