三路快排解法

将整块 分为 arr[l + 1, lt) < v; arr[lt, i) == v; arr[gt, r] > v

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

int n, k;
const int N = 100010;
vector<int> arr(N);


int quickSort(int l, int r, int k) {
    if (l == r) {
        return arr[l];
    }
    int v = arr[l];
    int lt = l;
    int i = l;
    int gt = r + 1;
    while (i < gt) {
        if (arr[i] < v) {
            swap(arr[lt + 1], arr[i]);
            lt ++;
            i ++;
        } else if (arr[i] > v) {
            swap(arr[gt - 1], arr[i]);
            gt --;
        } else {
            i ++;
        }
    }
    swap(arr[l], arr[lt]);
    if (lt == k) {
        return arr[lt];
    } else if (lt < k) {
        return quickSort(gt, r, k);
    }
    // arr[l + 1, lt)
    // arr[lt, i)
    // arr[gt, r]

    return quickSort(l, lt - 1, k);
}
int main() {
    cin >> n >> k;

    for (int i = 0; i < n ; i++) {
        cin >> arr[i];
    }
    cout << quickSort(0, n - 1, k - 1);

    return 0;
}