题目描述

给定一个长度为 n
的整数数列，以及一个整数 k
，请用快速选择算法求出数列从小到大排序后的第 k
个数。

输入格式
第一行包含两个整数 n
和 k
。

第二行包含 n
个整数（所有整数均在 1∼109
范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第 k
小数。

数据范围
1≤n≤100000
,
1≤k≤n

关键点在于k，第k就说明在哪部分。因为第一轮排序其实趋势就出来。
上半部分就是比下半部分边小，剩下的就是判断 k 是属于判断在上半部分 就跑上半部分，下半部分排序没啥效果 k 在下半部分也一样

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k;
int q[N];
void quick_sort(int q[],int l,int r)
{
  if(l>=r) return;
  int x=q[l+r>>1],i=l-1,j=r+1;
  while(i < j)
  {
    do i++;
    while(q[i]<x);
    do j--;
    while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
  }
  if(k <=j+1) quick_sort(q,l,j);
  else quick_sort(q,j+1,r);
}
int main()
{
  cin>>n>>k;
  for(int i=0; i<n; i++) cin>>q[i];
  quick_sort(q,0,n-1);
  cout<<q[k-1]<<endl;
  return 0;
}