题解 | #整数无序数组求第K大数#

//快排稍作修改，优化：无需对整个数组完整排序

//只用在包含目标值的区间中递归排序

#include <iostream>
#include<cstdlib> 
using namespace std;

void swap(int &a,int &b){//交换元素
    int temp=a;
    a=b;
    b=temp;
} 
int qsort(int A[],int l,int r,int k){
    if(l>=r)return A[l];
    int random=l+rand()%(r-l+1);
    int key=A[random],i=l,j=r; 
    swap(A[random],A[l]);//随机将一个元素与A[l]交换

    while(i<j){
        while(i<j&&A[j]>=key)//从右往左找到第一个比key小的
        j--;
        while(i<j&&A[i]<=key)//从左往右找到第一个比key大的
        i++;
        swap(A[i],A[j]);
    }
    swap(A[i],A[l]);//将A[l]放入正确位置
    
    if(i>k)return qsort(A,l,i-1,k);//递归,:只对存在A[k]的区间排序
    else if(i<k)return qsort(A,i+1,r,k); 
    else return A[i];
}
int main(){
    int k;
    int a[1000];
    char c='0';
    int i=0;
   while(c!='\n'){//读到换行为止
       scanf("%d",&a[i++]);
       scanf("%c",&c);
    };
    scanf("%d",&k);
    printf("%d",qsort(a,0,i-1,i-k));
    return 0;
}