$\Huge\color{orchid}{点击此处获取更多干货}$

快速排序

选取第k个数，比较常规的方法是先整体排序，然后输出第k个，这里介绍一种非常规方法，其实也是利用了快速排序的特点
快速排序有一个划分过程，确定了枢值之后，两半区段的长度也可以确定下来，此时第k位的搜索可以剪枝，如果左半区的长度比k小，那么第k个数一定不在左半区，反之则一定不在右半区，之后就跟快速排序一样，对左右两半再次划分，继续搜索
详情见下图和注释（只演示第一轮划分，之后以此类推）

C++ 代码

#include <iostream>
#include <functional>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int* arr = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    function<int(int, int, int)> kthElement
        = [&](int left, int right, int k)-> int {
            if(left >= right) {
                return arr[left];
            }
            int low = left - 1, high = right + 1;
            int mid = (low + high) / 2, pivotKey = arr[mid];
            while(low < high) {
                do {
                    low++;
                } while(arr[low] < pivotKey);
                do {
                    high--;
                } while(arr[high] > pivotKey);
                if (low < high) {
                    swap(arr[low], arr[high]);
                }
            }
            /*
            * 划分的时候已经能确定两部分的长度
            * 那么如果k不大于左半区的长度，就可以从左半区中选第k位
            * 否则，需要在右半区内选，位序为k - len
            * len是左半区的长度
            */
            if (high - left + 1 >= k) {
                return kthElement(left, high, k);
            } 
            else {
                return kthElement(high + 1, right, k - high + left - 1);
            }
        };
    cout << kthElement(0, n - 1, k) << endl;
    delete[] arr;
    return 0;
}