快排-P1923求第 k 小的数

快排应用

P1923 【深基9.例4】求第 k 小的数
题目来源：洛谷题库1923

思路：
数据量5*1e6 普通的冒泡、选择不行，数据范围大，计数排序也不行，考虑快排

参考代码

手写快排

#include <bits/stdc++.h>
using namespace std;
const int N = 5*1e6+5; 
int n,k;//第k小的数
int a[N],res=0;
void qsort(int l,int r){if(l==r) {res = a[l];return ;}else{int mid = a[(l+r)/2];int i=l,j=r;do{while(a[i]<mid) i++;while(a[j]>mid) j--;if(i<=j){swap(a[i],a[j]);i++,j--; }}while(i<=j);if(k<=j) qsort(l,j);//只需要排序zuo区间 else if(k>=i) qsort(i,r); //只需要排序you区间 else {res = a[k] ; //刚好处在j i中间的 return;}}
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr); 辅助cin cout-加快读写 cin>>n>>k;for(int i=0;i<n;i++){scanf("%d",&a[i]); //数据比较大，有点危险，需要快速读写，否则TEL }qsort(0,n-1);cout<<res; return 0;
} 

参考代码

直接套函数

ios::sync_with_stdio(false);cin.tie(nullptr); //辅助cin cout-加快读写 cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);cout<<a[k];