第k小的数

题目链接： https://www.acwing.com/problem/content/788/

#include<iostream>

using namespace std;

const int N = 1E5 + 5;
int n, k;
int arr[N];

int qsort(int l, int r){
    if(l >= r) return arr[l];
    int x = arr[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        while(arr[++ i] < x);
        while(arr[-- j] > x);
        if(i < j) swap(arr[i], arr[j]);
    }
    if(k <= j) return qsort(l, j);
    return qsort(j + 1, r);
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> arr[i];
    int val = qsort(1, n);
    cout << val;
    return 0;
}

第k大的数

题目链接: https://www.acwing.com/problem/content/4785/

#include<iostream>

using namespace std;

const int N = 1E5 + 5;
int n, k;
int arr[N];

int qsort(int l, int r){
    if(l >= r) return arr[l];
    int x = arr[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        while(arr[++ i] > x);
        while(arr[-- j] < x);
        if(i < j) swap(arr[i], arr[j]); 
    }
    if(k <= j) return qsort(l, j);
    return qsort(j + 1, r);
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> arr[i];
    int val = qsort(1, n);
    cout << val;
    return 0;
}