快速选择排序

快排的简单回顾
这是一种基于快速排序的应用算法，我们先来回顾一下快速排序快速排序模板
快排有三个步骤
0、选择一个支点；
1、根据指点将整个数组划分为两部分，第一部分为小于等于支点x的数，另一部分为大于等于支点x的数；
2、递归调用函数，对左右两边进行排序；

快速选择算法
快速选择算法是基于快排的，快排第三步是对左右两个区间同时进行递归，而快速选择算法可以根据要查找的数据对区间进行一种缩小；

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n,q[N];

int quick_sort(int q[],int l,int r,int k)
{
    if(l>=r)    return q[l];
    int x = q[(l+r)/2];
    int i = l-1, j = r + 1;
    while(i < j)
    {
        while(q[++i] <x);
        while(q[--j]>x);
        if(i <j)swap(q[i],q[j]);
    }
    if(j-l+1>=k)return quick_sort(q,l,j,k);
    else
        return quick_sort(q,j+1,r,k-(j-l+1));
}
int main(void)
{
    int k = 0;
    cin>>n>>k;
    for(int i = 0 ; i < n; i ++ )cin>>q[i];
    cout<<quick_sort(q,0,n-1,k)<<endl;
    return 0;
    
}

代码分析

    if(j-l+1>=k)return quick_sort(q,l,j,k);
    else
        return quick_sort(q,j+1,r,k-(j-l+1));

首先这个k是我们要查找的第k个数，在函数调用的时候，j将是左边区间最右边的下标，j-l+1就是左边区间的的元素的个数，如果k比左边区间的个数大，则我们应当递归右边的区间，去查中第k-（j-l+1)和数；