求助大佬，为什么超时

btlazzq @ 2021-11-09 00:48:59

#include<iostream>
#include<cmath>
using namespace std;
const int N=5000010 ;
int a[N];

void quick_sort(int a[],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]);
        else break;
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r);
}

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    printf("%d",a[k]);

    return 0;
}

by ZZ_peng09 @ 2021-11-09 06:43:00

快排需要优化 @btlazzq

by ZZ_peng09 @ 2021-11-09 06:45:09

因为只需求一个数，在左即只需搜左区间，在右区间只需要搜右区间，如果在中间区间直接输出

by btlazzq @ 2021-11-11 13:42:51

#include<iostream>
using namespace std;

const int N=500010;
int a[N];

int quick_sort(int a[],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]);
    }
    if(j-l+1>=k)return quick_sort(a,l,j,k);
    else return quick_sort(a, j + 1, r, k - (j - l + 1));
}
int main()
{
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    cout<<quick_sort(a,0,n-1,k)<<endl;

    return 0;
}

@ZZ_peng09 大佬，你看看我这样咋错了