解题思路

首先回顾一下快速排序的主要步骤：
① 找到分界点x：q[L] q[(L+R)/2] q[R] 三种方法都可以
② 左边所有数Left≤x  右边所有数Right≥x
③ 递归排序Left，递归排序Right

本道题中，采用快速选择算法，与快速排序算法的不同之处在于：
快速排序算法需要递归两边数据，而快速选择算法只需选择一边递归即可：
① k ≤ SL 递归Left
② k ＞ SL 递归Right
快速选择算法的时间复杂度为O(n)

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, k; // n表示一共有n个数，选择第K小的数作为输出结果
int q[N]; // q[N]表示所有的数

int quick_sort(int l, int r, int k)
{
    // 快速选择算法
    if (l == r) return q[l]; //如果只有一个数，直接返回

    int x = q[l], i = l - 1, j = r + 1; 
    //对x的赋值方法有三种选择，任选其中一种即可；i和j为两个指针，在指针进行运作前，需要先将他们所指的范围分别扩大一个单位，即l减去1，r加上1，这样才能保证指针在真正扫描数组前，已经移动过一位。
    while (i < j)
    {
        while (q[ ++ i] < x);
        while (q[ -- j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    int sl = j - l + 1; // 左边区间的数的个数为sl
    if (k <= sl) return quick_sort(l, j, k); // 在左边的区间中选择第 K 个小的数

    return quick_sort(j + 1, r, k - sl); // 在右边的区间中选择第 k-sl 小的数
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> q[i]; // 读取所有的数

    cout << quick_sort(0, n - 1, k) <<endl; // 输出第k小的数
}