0pts求调

LiJoQiao @ 2023-06-24 14:07:23

#include<iostream>
using namespace std;
const int MAXN=5000010;
int a[MAXN],k,n;
void _qsort1(int l,int r)
{
    int mid=a[(l+r)/2],i=l,j=r;
    while(i<=r)
    {
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=r)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(k<=j)_qsort1(l,j);
    else if(k>=i)_qsort1(i,r);
    else
    {
        cout<<a[j+1];
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    _qsort1(1,n);
    return 0;
}

by dengruixun @ 2023-07-02 21:54:10

建议你用快速排序 参考快速排序：

#include<iostream>
using namespace std;
void QuickSort(int *arr,int low,int high){
    if(low<high){//不加这个条件会死循环 
        int i=low;
        int j=high;
        int key=arr[low];
        while(i<j){
            while(i<j&&arr[j]>=key)
                j--;
            if(i<j) 
                arr[i++]=arr[j];//先赋值在自增 
            while(i<j&&arr[i]<key)
                i++;
            if(i<j)
                arr[j--]=arr[i];//先赋值在自减 
        }
        arr[i]=key;
        QuickSort(arr,low,i-1);//给左边排序 
        QuickSort(arr,i+1,high);//给右边排序 
    }
}
int main(){
    int a[100000], n;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    QuickSort(a,0,n-1);
    int i;
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

by dengruixun @ 2023-07-03 09:19:43

#include<iostream>
using namespace std;
int n, k;
void QuickSort(int a[], int left, int right){
    int swap;
    int i = left, j = right, pivit = a[left];
    do{
        while(a[i]<pivit){   //从左边找比pivit大于等于的数 
            i++;
        }
        while(a[j]>pivit){   //从右边找比pivit小于等于的数 
            j--; 
        }
        if(i<=j){            //交换位置然后i++， j-- 
            swap = a[i];a[i] = a[j];a[j] = swap;
            i++;
            j--;
        }
    }while(i<=j);
    if(k<=j){       //在左区间只需要搜左区间
    QuickSort(a, left, j);
    } 
    else if(i<=k){
    QuickSort(a, i,right);  //在右区间只需要搜右区间
    }else{           //如果在中间区间直接输出
        printf("%d",a[j+1]);
        exit(0);
    }
}
int main(){
    scanf("%d%d", &n, &k);
    int a[n];
    for(int i = 0;i<n;i++){
        scanf("%d", &a[i]);
    }
    QuickSort(a, 0, n-1);
    cout<<a[k];
    return 0;
}