快速排序
- 确定分界点 $q[l],q[l+r>>1],q[r]$, 随机选择设置为 $x$
- 调整区间:分为 :
$\;\;\;\;\;$[…,x] $\;\;\;\;$和$\;\;\;\;$ [x,…]
|-------------------|------------------| - 递归处理左右两边
- 暴力解法
- 开两个数组 $a[\;\; ] ,b[ \;\;]$
- 遍历 $q[l$ ~ $r]$
- 如果 $q[i] ≤ x$ ,则将 $x$ 放入 $a[\;\; ]$
- 如果 $q[i] ≥ x$ ,则将 $x$ 放入 $b[\;\; ]$
- 把 $a[\;\; ]$ → $q[\;\; ]$,$b[\;\;]$ → $q[\;\; ]$
- 更优做法
- 用两个指针,$i = l - 1 \;\;\; j = r + 1;$
- 从前往后遍历,直到找到第一个 $q[i] ≥ x$ 的数,从后往前遍历直到找到第一个 $q[i] ≤ x$ 的数,两者进行$swap()$
模拟图:
第k个数:排序完输出a[k - 1]就可以了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define int ll
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define MOD 1e9 + 7
using namespace std;
int read()
{
int w = 1, s = 0;
char ch = getchar();
while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';ch = getchar(); }
return s * w;
}
//最大公约数
int gcd(int x,int y) {
if(x<y) swap(x,y);//很多人会遗忘,大数在前小数在后
//递归终止条件千万不要漏了,辗转相除法
return x % y ? gcd(y, x % y) : y;
}
//计算x和y的最小公倍数
int lcm(int x,int y) {
return x * y / gcd(x, y);//使用公式
}
int ksm(int a, int b, int mod) { int s = 1; while(b) {if(b&1) s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 100010;
int a[N];
void qsort(int a[], int l, int r) {
if (l >= r) return;
//将第一个定位分界值。
int x = a[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (a[i] < x);//找到小于x的值为止
do j--; while (a[j] > x);//找到大于x的值为止
if (i < j) swap(a[i], a[j]);//交换
}
//递归左右两边
qsort(a, l, j);
qsort(a, j + 1, r);
}
signed main()
{
int n = read(), k = read();
for (int i = 0; i < n; i++) a[i] = read();
qsort(a, 0, n - 1);
printf("%lld", a[k - 1]);
return 0;
}