求助,快排做法,不知道哪里错了

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

qwq2519 @ 2021-06-18 23:51:05

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i <=k ; ++i)
#define drp(i,j,k) for(register int i(j);i >=k ; --i)
using namespace std;
inline char gt()
{
    static char buf[1 << 21], *p1 = buf , *p2 = buf;
    return p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf , 1 , 1 << 21, stdin ), p1 == p2);
}
template < typename T >
inline void read( T &x )
{
    x = 0;
    register char ch = getchar();
    int w = 0;
    while(!(ch >= '0' && ch <= '9'))  w |= ch == '-', ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
    w ? x = ~(x - 1) : x;
}
template<typename T>
inline void out(T x)
{
    if(x < 0) putchar('-'), x = -x;
    char s[20];
    int num(0);
    while(!num || x) s[++num] = x % 10 + '0', x /= 10;
    while(num) putchar(s[num--]);
    putchar(' ');
}
const int MAX = 1e6 + 79;
int N, k;
int a[MAX];

void Quick_Sort(int *q, int l, int r, int t)
{
    int cnt = 0;
    if(l >= r) {
        cout << q[l] << ' ';
        return ;
    }
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while(i < j) {
        while(q[++i] < x) cnt++;
        while(q[--j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    if(cnt == t) {
        cout<<x<<' ';
        return;
    }
    if(cnt > t)Quick_Sort(q, l, j, t);
    else Quick_Sort(q, j + 1, r, t - cnt);
}

int main()
{

    cin >> N >> k;
//  read(N);read(k);
    rep(i, 1, N)cin >> a[i];
//  read(a[i]);
    Quick_Sort(a, 1, N, k + 1);
    return 0;
}

我的快排可能比较奇怪。。。不是边递归边计数吗,不断二分找到目标区间。。不知道哪里错了,思路是对的。。但是细节不知道哪里错了


|