求助,为什么快排这个地方用<=能过,但是<不能过?

P1923 【深基9.例4】求第 k 小的数

Nobody_Zhang @ 2021-09-10 16:22:44

AC代码:

#include<bits/stdc++.h>
using namespace std;
int a[5000005],n,k;
void qsort(int l,int r)
{
    if(l==r)
    {
        cout<<a[k]<<endl;
        exit(0);
    }
    int i=l,j=r,tmp=a[l];//相等的时候就直接用if给判出去了
    while(i!=j)
    {//从小到大
        while(a[j]>=tmp&&i<j) j--;
        while(a[i]<=tmp&&i<j) i++;
        swap(a[i],a[j]);
    }
    swap(a[l],a[i]);
    if(i==k){
        cout<<a[i]<<endl;
        exit(0);
    }
    if(i<k){
        qsort(i+1,r);
    }
    if(i>k){
        qsort(l,i-1);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    //cin>>n>>k;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
        //cin>>a[i];
    random_shuffle(a,a+n);
    qsort(0,n-1);
    return 0;
}

UAC代码:

#include<bits/stdc++.h>
using namespace std;
int a[5000005],n,k;
void qsort(int l,int r)
{
    if(l==r)
    {
        cout<<a[k]<<endl;
        exit(0);
    }
    int i=l,j=r,tmp=a[l];//相等的时候就直接用if给判出去了
    while(i!=j)
    {//从小到大
        while(a[j]>tmp&&i<j) j--;
        while(a[i]<tmp&&i<j) i++;
        swap(a[i],a[j]);
    }
    swap(a[l],a[i]);
    if(i==k){
        cout<<a[i]<<endl;
        exit(0);
    }
    if(i<k){
        qsort(i+1,r);
    }
    if(i>k){
        qsort(l,i-1);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    //cin>>n>>k;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
        //cin>>a[i];
    random_shuffle(a,a+n);
    qsort(0,n-1);
    return 0;
}

by 天南星魔芋 @ 2021-09-10 16:55:17

@Nobody_Zhang 因为你的 i 不会增加,快排变成了冒泡


|