算法

快速排序

C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;
int q[N];

int quick_sort(int l, int r, int k) 
{
    if(l == r) return q[l];         //找到之后返回q[l] = q[r] (第k小的数)

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];      //尽量直接取中间值 避免x取左右两边的数字时出现死循环的情况
    while(i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    int sl = j - l + 1;         //sl表示排序之后左边的个数  类似于二分 每次寻找第k小的数字在哪边  在那边就排哪边
    if(sl >= k) return quick_sort(l, j, k);     //在左边 排序左边
    return quick_sort(j + 1 , r, k - sl);       //在右边 排序右边  第k小的数 变成k - sl  
}

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i ++) cin >> q[i];        

    int ans = quick_sort(0, n - 1, m);      //利用快排 在 0 ~ n - 1 之间找第k小的数

    cout << ans << endl;

    return 0;
}