题目描述

样例

算法1

快排优化

时间复杂度

C++ 代码

include[HTML_REMOVED]

define ll long long

using namespace std;
const int N = 8e6+5;
int num[N];
void qsort(int num[],int l,int r,int k){
if(l >= r){
return;
}
int mid = l+r>>1;
int base = num[mid];
int i = l-1,j = r+1;
while(i < j){
do i++;while(num[i] < base);
do j–;while(num[j] > base);
if(i < j)swap(num[i],num[j]);
}
int ans = j-l+1;//前面半段数组有几个元素
if(k <= ans)qsort(num,l,j,k);
else qsort(num,j,r,k-ans);
}
int main(){
int n, k;
cin>>n>>k;

for(int i = 0;i < n;i++){
    //cin>>num[i];
    scanf("%d",&num[i]);
}

qsort(num,0,n-1,k);
printf("%d",num[k-1]);
return 0;

}