是我快排写错了吗 ？怎么输出空白

彬腾向前冲 @ 2021-08-17 14:39:10

#include <bits/stdc++.h>

using namespace std;

int m,k;
int a[5000001];

void quick_sort(int a[],int l,int r)
{
    if (l >= r) return;

    //确定边界
    int i = l-1 ; int j = r+1;int x = a[r+l>1]; 
    if (i < j){
        do i ++ ; while (a[i]<=x);
        do j ++ ; while (a[j]>=x);
        swap (a[i],a[j]);
    }
    quick_sort (a,l,j),quick_sort(a,j+1,r);
}

int main ()
{
    cin >> m >> k;
    for (int i = 0; i < m; i ++) cin >> a[i];

    quick_sort(a,0,m-1);

    cout << a[k];

    return 0;
}

by Super_Cube @ 2021-08-17 14:43:14

快排求序列第k小.

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],k;
int P(int l,int r){
    int i=l,j=r;
    int t=a[l];
    while(i<j){
        while(j>i&&a[j]>=t)j--;
        while(i<j&&a[i]<=t)i++;
        swap(a[i],a[j]);
    }swap(a[l],a[i]);
    return i;
}
int qs(int l,int r){//quick_sort
    if(l==r)return a[l];
    else if(l<r){
        int t=P(l,r);
        if(t==k)return a[k];
        else if(t>k)return qs(l,t-1);
        else return qs(t+1,r);
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;cin>>a[i++]);
    cout<<qs(1,n);
    return 0; 
}

by lprer @ 2021-08-17 14:43:27

       do i ++ ; while (a[i]<=x);
       do j ++ ; while (a[j]>=x);

这段错了？

by 彬腾向前冲 @ 2021-08-17 17:05:41

@c18958781557 没有啊

by lprer @ 2021-08-17 18:57:16

@彬腾向前冲

do j ++ ; while (a[j]>=x);

->

do j -- ; while (a[j]>=x);

也许我太菜了，不会快排...

by wangsongsong @ 2021-08-25 21:51:45

应该是数组开太大了，爆了

by LeTu_Jun @ 2021-08-30 17:09:58

@彬腾向前冲 为啥不用sort

by 彬腾向前冲 @ 2021-08-30 22:57:07

@和国家干部 sort有的题要被卡

by LeTu_Jun @ 2021-08-31 09:36:22

@彬腾向前冲 这题好像sort+氧气能过