要从一个数组中找出第k小的元素，最容易想到的是快速排序，但是快速排序解决这个问题有很多不必要的操作，在快速排序中，根据“哨兵”元素把数组分成两部分，然后对两部分进行递归处理，第k个顺序统计量的算法也借鉴这种思路，我们称为“快速选择(quick select)算法”,但是快速选择算法每次只需要处理第K个元素所在的那一部分就行，我们的目的只是找到目标元素，随着递归次数的深入，快速选择算法要处理的元素会越来越少（而快速排序随着递归的深入，每次递归处理的元素总数依然是n），这种差别是很大的，后面分析时间复杂度时可以得知快速选择算法的期望运行时间是$\theta(n)$。

算法实现

快速选择算法跟快速排序类似，主要步骤就是分组算法：根据哨兵元素把数组分成两组，一组小于哨兵，一组大于哨兵，然后进行递归调用。

分组算法(partition)

下面是分组算法的java实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
  * 分组算法，返回哨兵元素s所在的下标，然后[left,s-1]这一组元素都小于等于哨兵元素，[s+1,right]这一组元素都大于哨兵元素
  * @param arr 要操作的数组
  * @param left 数组开始处理下标
  * @param right 数组结束处理下标
  * @return 哨兵元素对应的下标
  */
public int partition(int[] arr,int left,int right){
    // j用来指定哨兵最后应该插入的位置，j左边的元素都是小于哨兵的
    int j=left;

    // 随机指定一个元素作为哨兵,并把哨兵放到数组最后的位置方便处理
    int sindex=left+(int)((right-left)* Math.random());
    int s=arr[sindex];
    arr[sindex]=arr[right];
    arr[right]=s;

    // 注意这里只在指定下标范围内循环，适用递归，而不是整个数组
    for (int i = left; i <= right; i++) {
        //如果当前遍历的元素小于等于哨兵，则把它跟当前哨兵下标对应的元素交换，然后递增哨兵下标，始终保持j左边元素小于等于哨兵
        if(arr[i]<=s){
            int a=arr[i];
            arr[i]=arr[j];
            arr[j]=a;
            j++;
        }
    }
    // 遍历完成后，返回j，表示哨兵下标，注意，当i遍历到right时，哨兵会跟自己比较，然后交换到j的位置，并使j++，
    // 而此时哨兵处在j的位置，所以我们最终应该返回j-1(不然j还可能会越界)
    return j-1;
}

下图可以帮助理解partition的运行原理： partition运行原理

快速选择算法

实现了上面的分组算法后，剩下的就很简单了，我们只需要根据哨兵的位置和k的相对关系选择性的递归调用即可，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
  * 快速选择算法，返回数组中第k小的元素
  * @param arr，输入数组
  * @param left  数组开始处理下标
  * @param right 数组结束处理下标
  * @param k 因为表示第k小的元素，所以从1开始计数
  * @return 返回数组中第k小的元素的值
  */
public int quickSelect(int arr[],int left,int right,int k){
    if(left==right) return arr[left]; // 如果数组只有一个元素，直接返回
    int sindex=partition(arr,left,right); // 返回哨兵的下标，此时数组已经初步排序为[左边部分，哨兵，右边部分]的递增形式
    if(sindex-left+1==k) return arr[sindex]; // 如果哨兵正好在第k个位置，则返回
    else if(sindex-left+1<k){ // 如果哨兵位于k的左边，说明目标元素在右边部分的第(k-sindex)的位置
        return quickSelect(arr,sindex+1,right,k-(sindex-left+1));
    }else{ // 如果哨兵位于k的右边，说明目标元素在左边部分的第k个位置
        return quickSelect(arr,left,sindex-1,k);
    }
}

期望运行时间

运行一次快速选择算法，可能出现的最差情况：比如我们的目标是选择最小元素，但每次递归调用分组算法都只排除了一个最大元素，直到最后一次循环才选中目标元素，那么运行时间是$\theta(n^2)$,所以单说快速选择算法的时间复杂度，我们只能给出$O(n^2)$，但是类似快速排序，在样本数量足够大的时候，快速选择算法的期望运行时间是$\theta(n)$，下面来证明这个结论。

对于一个大小为n的数组，我们用符号$T(n)$表示一次快速选择算法运行的时间,根据前面的代码，可以得出一个基本的递归式(注意left在这里表示数量而不是下标)：

$$ \begin{aligned} T(n)= \begin{cases} T(left)+\theta (n),&k-1<left \\ T(n-1-left)+ \theta (n),&k-1>left \\ O(1)+ \theta(n),&k-1==left \end{cases} \end{aligned} $$

其中$\theta(n)$表示partition方法运行的时间，partition只有一个for循环，$k$表示我们要找的是第k个元素(从1开始)，left表示在哨兵左边的元素数量，取值[0,n-1],n-1-left就表示在哨兵右边的元素数量。

因为partition操作是随机的，所以left的值（也就是哨兵左边的元素数量）会在[0,n-1]中等概率的出现，而根据上面的公式可知，对于任意的$k$,只要知道left的值，就知道了需要递归处理的元素是哪些，而$E[T(n)]$就是把所有可能出现的left对应的情况进行统计，分析它们对应要递归处理的元素的数量。这里要注意，虽然left的值是在[0,n-1]之间变化的，但是要递归处理的元素数量并不是单调变化的，它们在k的两侧都会发生突变，看下图：

递归处理的元素数量

从图中可以观察到，当left处于s1或者s4时，处理的数据量是相同的，都大于(n-1)/2,s2要处理的数据量也大于(n-1)/2，而s3要处理的数据量小于(n-1)/2。

问题是s1-s4这4个区域的具体大小都跟k的取值有关，我们要想办法让$E[T(n)]$跟k无关。从图中可以看到(s1+s2)和(s3+s4)的值跟k无关，而s1跟s4的情况是相关的，我们想办法让s2的情况跟s3相同，因为s2要处理的数量大于s3，所以用s2去替换s3来得到一个更宽松的上界，即(left在s1-s4中遍历一次处理的数据量)<=(left在2*(s1+s2)中遍历一次处理的数据量)，得：

$$ E[T(n)]<=2 \sum \limits_{ s=\lceil \frac{n-1}{2}\rceil}^{n-1}\frac{1}{n}T(s)+\theta (n)=\frac{2}{n}\sum\limits_{ s=\lceil \frac{n-1}{2}\rceil }^{n-1}T(s)+\theta (n) $$

公式中使用向上取整就可以覆盖到n是奇数和偶数两种情况。

要证明上面的递归式，我们用替代法，替代法最重要的步骤就是猜，猜出算法的时间复杂度，然后代入到方程中求证，猜测通常需要一点经验，这里我们的猜测是：当n足够大时，存在一个常数a，使得$T(n)< an $成立，因为递归式中还有$\theta (n)$部分，所以用$bn$来代替它的上限，对上面的方程整理后得:

$$ \begin{aligned} E[T(n)]<=&\frac {2a}{n}\frac {(n-1+\lceil \frac {n-1}{2} \rceil )}{2}(n- \lceil \frac {n-1}{2}\rceil )+ bn \\ <=&\frac {a}{n}(n-1+\frac {n}{2})(n-\frac {n}{2})+bn \\ =&\frac {3}{4}an-\frac {a}{2}+bn \\ =&an+(bn-\frac {a}{2}-\frac {1}{4}an) \end{aligned} $$

还要满足$(bn-\frac{a}{2}-\frac{1}{4}an)<=0$，整理后得$n>=\frac{2a}{a-4b}$,也就是说，当n大于这个值时，$E[T(n)]<=an$就成立，这个式子的值虽然跟a,b有关，但是a的值是我们假设的，b的值可以认为是固定的，那么我们只要让a远大于4b就行了，此时式子的值接近2，而n=1,2的情况显然是满足条件的，至此证明结束。