快速选择算法——第k个数

快速选择算法可以快速选出无序数列第k大(小)的数，比起快速排序，它的时间复杂度更优秀，达到了O(N)级别

他的思想和快速排序极为相似，都是基于分治的三步走 对于在区间[L,R]选出第k小数的问题,处理方式如下：

1. 在[L,R]上任取一个基准数x
2. 用和快速排序一样的方法将x归位
3. 我们将x归位后，比x小的数的个数记为SL，此时分类讨论:
   1. 如果k<=SL,则说明目标数在x左侧区间里，我们递归寻找，即在左侧区间寻找第k小数，此时不再需要处理右侧区间
   2. 如果k>SL,则说明目标数在x右侧,此时我们向右侧递归，而问题变成了在右侧区间寻找第k-SL小的数

对于时间复杂度的讨论: 第一次操作是扫面整个数列，时间是N，第二次是对一个子区间操作，时间是N/2,然后是N/4,以此类推，时间是

\sum_{i=0}^{d}N(\frac{1}{2})^{i}\le 2N

此时的复杂取O(N)就好

源码

void q_select(int a[],int l,int r,int k){
    //在数组a的区间l,r中，寻找第k小数
    if(l>=r)
        return ;
    int x=a[(l+r)/2],i=l-1,j=r+1;
    while(i<j){
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j)
            swap(a[i],a[j]);
    }
    //以上部分和快速排序一样，找基准数，然后令其归位
    int SL=j-l+1;   //SL是比x小的数的个数
    if(k<=SL)
        q_select(a,l,j,k);
    else
        q_select(a,j+1,r,k-SL);
}