题目

对 n 个元素的数组 a，进行从小到大排序

#include<bits/stdc++.h>
using namespace std;

const int N = 1E5 + 5;

int a[N];

void quick_sort(int l, int r) {
    // 递归的终止情况
    if (l >= r) return;
    // 第一步：分成子问题
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        // 若从大到小，则这判断反过来
        do ++ i; while (a[i] < x);
        do -- j; while (a[j] > x);

        if (i < j) swap(a[i], a[j]);

    }
    // while 循环结束后，q[l..j] <= x,q[j+1..r] >= x
    //第二步：递归处理子问题
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
    }

    quick_sort(0, n - 1);

    for (int i = 0; i < n; ++ i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

题目
给定 n 个无序数
用快排找出从小到大排序后的第 k 个数

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int a[N];

int quick_sort(int l, int r, int k) {

    // 只有一个数时，即要找的数
    if (l >= r) return a[l];

    int x = a[l + r >> 1], i = l - 1, j = r + 1;

    while (i < j) {
        do ++ i; while (a[i] < x);
        do -- j; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    // 左边元素个数 = j - l + 1
    // 如果 左边 元素个数大于 k 从左边找
    // 否则从 右边 找第 k - (左边元素个数) 的数
    if (j - l + 1 >= k) return quick_sort(l, j, k);
    else return quick_sort(j + 1, r, k - (j - l + 1));

}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
    }
    cout << quick_sort(0, n - 1, k) << endl;

    return 0;
}