当你学会快速排序中的关键步骤：划分区间的操作后，你可能会想：它除了可以将一个区间按照某一标准划分为两半，还有其它的应用吗？答案是有的，快速选择第k大的数就是它的另一个应用
....

题目要求

给定一个长度为n的整数数列，以及一个整数 k，求出数列从小到大排序后的第 k个数。即：从数列中尽可能快的找出第k小的数。

分析题目

根据上述题目的要求，如果使用排序后，再找第k个数的最低时间复杂度是nlogn的，那么可不可以不通过排序直接得到第k小的数呢？

根据快速排序中的划分操作，可以知道每一次操作都会把不大于pivot的数放到其左边，把不小于pivot的数放到其右边，每一次都会将一整个数列划分为两组，如果在这个基础上可以知道在pivot的左半边有几个数，就可以知道pivot是第几个小的数，因此就可以判断第k小的数是位于左半边还是右半边，直接就可以舍弃一半的搜索范围。

根据上述描述， 可以得到其时间复杂度为O(N)，因为其时间复杂度是一个等比数列求和。

快速选择算法

算法流程

1. 随机选择一个pivot 进行二分，即：快速排序的划分算法
2. 统计在划分点pivot 左侧的数的个数，看它与要选择的第k个数的k的大小来缩小搜索区间，以此为基准来判断是选择左半边进行搜索还是右半边进行搜索
3. 根据夹挤准则，得到第k小的数

算法的实现

该算法的实现有多种版本，只需要能把上述算法流程实现即可。这个算法使用递归来实现比较简单，需要注意递归的三要素：

• 递归的定义
• 递归的出口
• 递归的拆解

下面几个版本，均要求所求问题的解一定存在，否则代码会出现一些问题。

版本01

#include <bits/stdc++.h>

const int N = 1e5 + 10;
int ary[N] = {0};

int quickSelect(int ary[], int lo, int hi, int k) {
    // 03.直接比较个数，当最后是1个的时候，直接返回该区间的第一个元素，就是答案
    if (k <= 1) {
        return ary[lo];
    }
    
    // 01.划分区间
    int left = lo - 1, right = hi + 1;
    int pivot = ary[left + (right - left) / 2];
    
    while (left < right) {
        do ++left; while (ary[left] < pivot);
        
        do --right; while (ary[right] > pivot);
        
        if (left < right) {
            std::swap(ary[left], ary[right]);
        }
    }
    
    // 02.由于外面没有减一，需要加1做调整，然后统计左侧数的个数，然后选择合适的区间进行搜索
    if (right + 1 - lo < k) {
        return quickSelect(ary, right + 1, hi, k - right - 1 + lo);
    } else {
        return quickSelect(ary, lo, right, k);
    }
}

int main() {
    int n = 0, k = 0; 
    scanf("%d%d", &n, &k);
    
    
    for (int i = 0; i < n; ++i) {
        scanf("%d", &ary[i]);
    }
    
    int num = quickSelect(ary, 0, n - 1, k);
    printf("%d", num);
    
    return 0;
}

版本02

该版本的作者是yxc

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
int q[N];

int quick_select(int l, int r)
{
    // 03.夹挤准则得到最后答案
    if (l == r) return q[l];

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
	
    // 将第k小的数，与划分边界进行比较，因为是提前减去1，所以可以直接比较
    // 不需要调整后再比较
    if (k <= j) return quick_select(l, j);
    return quick_select(j + 1, r);
}

int main()
{
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
	
    // 提前减1，因为划分后，需要比较边界值，而其划分的边界选择的是闭区间
    // 所以需要提前减1
    k -- ;
    cout << quick_select(0, n - 1) << endl;

    return 0;
}

版本03

可以根据01和02可以得到一个版本3：

#include <bits/stdc++.h>

const int N = 1e5 + 10;
int ary[N] = {0};

int quickSelect(int ary[], int lo, int hi, int k) {
    // 03.此时答案集合里面只有一个唯一解，该解就是答案
    if (lo == hi) {
        return ary[lo];
    }
    
    // 01.划分区间
    int left = lo - 1, right = hi + 1;
    int pivot = ary[left + (right - left) / 2];
    
    while (left < right) {
        do ++left; while (ary[left] < pivot);
        
        do --right; while (ary[right] > pivot);
        
        if (left < right) {
            std::swap(ary[left], ary[right]);
        }
    }
    
    // 02.由于外面没有减一，需要加1做调整，然后统计左侧数的个数，然后选择合适的区间进行搜索
    if (right < k - 1) {
        return quickSelect(ary, right + 1, hi, k);
    } else {
        return quickSelect(ary, lo, right, k);
    }
}

int main() {
    int n = 0, k = 0; 
    scanf("%d%d", &n, &k);
    
    
    for (int i = 0; i < n; ++i) {
        scanf("%d", &ary[i]);
    }
    
    int num = quickSelect(ary, 0, n - 1, k);
    printf("%d", num);
    
    return 0;
}