问题描述

对于给定的含有n个元素的无序序列，求这个序列中第k(1≤k≤n)小的元素

算法分析

这个算法用了分治法的思想，具体来说是一种折半查找/二分查找的方法，如果熟悉快速排序的话，会觉得跟快速排序很像，具体来说思路就是选取一个元素作为枢轴（一般是第一个，当然还有随机取法），然后从两端交替往中间扫描，比枢轴元素大的元素就放到右边，比枢轴元素小的就放到左边，然后把枢轴元素放到中间，这样枢轴元素的位置就确定了，这样就得到了第i+1小的元素，然后如果要找的k比这个（i+1）大，就在右边区间再用这个方法寻找，如果要找的k比这个（i+1）小，就在右左边区间再用这个方法寻找。以此类推，直到找到第k小的元素（即i+1 = k）
这个过程中有几个很有意思的问题（如果不理解可以看下面的图示）：

• 为什么要左右交替的扫描，并且要先从右边开始扫描，因为枢轴左边是比枢轴小的元素，枢轴右边是比枢轴大的元素，刚开始把枢轴元素提取出来之后，就相当于有了一个空位，在右边扫描到的比较小的元素就可以放到这个空位，这个时候右边就相当于有了一个空位，再从左边扫描看到有大的元素就可以放到右边的空位。以此类推，左右交替扫描可以利用之前一次扫描移动元素留下的“空位”而不需要额外的辅助空间。
• 代码实现中直接把一个元素移动到另外一个位置，而不是做交换，这不会导致列表中出现两个相同的元素吗，并且原本那个位置的元素会消失，实际上这个问题跟上个问题有些关联，第一个被覆盖的元素是枢轴元素所在的位置（i=0位置），而枢轴元素已经被我们记录，并且最后会还原，所以不会消失，第二个被覆盖的元素是上一个找到的较小的那个元素，也就是复制了一份到枢轴元素位置的元素，以此类推，相当于一个向前的不断替换，最前面加了一个辅助空间记录枢轴，最后再把枢轴元素放回列表，这样就不会出现刚刚说到的两个问题了。

代码

/*
 * @Description: 分治法-寻找一个序列中第K小的元素
 * @Author: yumu
 * @TimeComplexityRecurrence: T(n) = T(n/2) + O(n) => T(n) = O(n)
 * @BestCaseTimeComplexity: O(n) 当每次划分的基准/枢轴恰好是中位数，也即正好能将一个序列划分为长度大致相等的两个子序列时是最好的情况
 * @WorstCaseTimeComplexity: O(n^2) 当每次划分的基准恰好是序列中的最大值或者最小值时，处理区间只比上一次减少1个元素，这是最坏的情况
 * @AverageCaseTimeComplexity: O(n)
 */
#include <stdio.h>
int QuickSelect(int *a, int start, int end, int k)
{
    // 如果要寻找的子序列中只有一个元素且这个元素正好是要找的第k小元素(这里能这样判断其实是因为,前面的寻找的过程其实都是在排序,能找到这一个的时候这个元素的位置绝对是正确的)
    if (start == end && start == k - 1)
    {
        return a[start];
    }
    // 这里其实还有一种找不到的情况，但是题目一般不会这样去给定k的值，而且目前的程序虽然不能处理超范围的值，但是也不会出错，其实主要是我懒得加了
    else if (start < end)
    {
        // 记录枢轴的值
        int pivot = a[start];
        // 用另外的变量来代替start和end避免破坏start和end的值,后面递归的时候还要用到
        int i = start, j = end;
        // 外层这个循环主要是保证进行多次循环，直到比枢轴元素大的元素都到枢轴元素的右边，比枢轴元素小的元素全部到枢轴元素的左边，也即是确定枢轴元素的位置
        while (i != j)
        {
            // 从右往左扫描，直到找到比枢轴元素小的元素
            while (j > i && a[j] >= pivot)
            {
                j--;
            }
            // 把比枢轴元素小的元素移动到左边的空位（第一个空位其实就是枢轴的位置）
            a[i] = a[j];
            // 从左往右扫描，直到找到比枢轴元素大的元素
            while (i < j && a[i] <= pivot)
            {
                i++;
            }
            // 把比枢轴元素大的元素移动到右边的空位
            a[j] = a[i];
        }
        // 把枢轴元素放回队列
        a[i] = pivot;
        // 找到了的情况
        if (i == k - 1)
        {
            return a[i];
        }
        // 要找的元素在右区间,对右区间继续递归查找
        else if (k - 1 > i)
        {
            return QuickSelect(a, i + 1, end, k);
        }
        // 要找的元素在左区间,对左区间继续递归查找
        else
        {
            return QuickSelect(a, start, i - 1, k);
        }
    }
}
int main()
{
    // 指定序列长度
    int n = 10;
    // 设置序列
    int a[] = {2, 5, 1, 7, 10, 6, 9, 4, 3, 8};
    int res;
    // 这里相当于是把所有的k都试了一遍,实际上一般只会问一个k值
    for (int k = 1; k <= n; k++)
    {
        res = QuickSelect(a, 0, n - 1, k);
        printf("第%d小的元素是%d\n", k, res);
    }
    return 0;
}

运行结果

代码流程图示

起始状态，枢轴为2，寻找第5小元素
第一次从右往左扫描
第一次从左往右扫描
至此i!=j，也就是说，第i+1小元素还没有确定（换句话说，快排的一趟还没有完成，还没有一个元素的位置得到确定），所以继续扫描
第二次从右往左扫描
到这里满足了i == j的条件，所以，不会再从左往右扫描了，直接跳出循环，把枢轴元素放回序列
至此其实相当于完成了快速排序的一趟，元素2的位置确定了，也即是第2小元素的位置确定了
显然，我们要寻找的元素位置 5 > 2 （其实就是说我们现在找到了第二小的元素，也就是2，但是我们要找的是第5小的元素），所以要在右区间进行递归查找，注意右区间是从i+1开始的，并且因为还是用跟刚刚一样的方法，所以枢轴要从新的列表中选取

第三次从右往左扫描

第三次从左往右扫描

第四次从右往左扫描
第四次从左往右扫描

第五次从右往左扫描
到这里满足了i == j的条件，所以，不会再从左往右扫描了，直接跳出循环，把枢轴元素放回序列
至此其实相当于又完成了快速排序的一趟，元素5的位置确定了，也即是第5小元素的位置确定了，至此我们已经找到了我们想找的元素

参考文献

《算法设计与分析（第2版）》, 李春葆, 清华大学出版社。