定义

在给定线性序集中n个元素和一个整数k，要求找出n个元素中第k小的数。

方法一

线性时间选择，可以使用堆排序，这样就可以在$O(n+klog_n)=O(n)_的时间内找到的k小的元素。

方法二

使用快速排序中的分块算法，对所需要选择的数组分块，分完以后再在剩余的部分中，寻找(k – 减去分块的大小)

代码如下:

template <class Type>
int Partition(Type a[], int p, int r)
{
    int i = p;
        j = r+1;
    Type x = a[p];
    while(1)
    {
        while(a[++i] < x);
        while(a[--j] > x);
        if(i >= j) break;
        swap(a[i], a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}
template <class Type>
int RandomPartition(Type a[], int p, int r)
{
    int i = Random(p, r);
    swap(a[i], a[p]);
    return Partition(a, p, r);
}
template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k)
{
    if(p == r) return a[p];
    int i = RandomPartition(a, p, r);
    j = i - p + 1; // 分块的大小
    if(k <= j) return RandomizedSelect(a, p, i, k);
    else return RandomizedSelect(a, i+1, r, k-j);
}

但是此方法在最差的情况下需要$n^2$的时间，比如在寻找最小元素时，总是在最大的元素划分。

尽管如此，平均效率还是不错的。

方法三

我还是比较喜欢直接看代码= =

template <class Type>
Type Select(Type a[], int p, int r, int k)
{
    if (r - p < 75)
    {
        sort(&a[p], &a[r]);
        return a[p+k-1];
    }
    for(int i = 0; i <= (r-p-4)/5; i++)
        Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
    int i = Partition(a, p, r, x);
    j = i - p + 1;
    if(k <= j) return Select(a, p, i, k);
    else return Select(a, i+1, r, k-j)
}