本篇源至于《算法导论》第９章学习笔记，记录关于顺序统计量的学习实践。
概念
顺序统计量
在一个由ｎ个元素组成的集合中，第ｉ个顺序统计量(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);
}
