核心算法:先切一半快排(交换左边大的和右边小的),然后在剩下两半里继续快排.
已注释关键行代码
#include<iostream>
using namespace std;
int n,k; /// 数据长度,题意所要第k个
const int N = 100010;
int nums[N]; // 数据存在这儿(数组)
void qs(int q[], int l, int r) // argument参数:数据,(要排序的)左端点,右端点
{
if (l >= r) return; // 如果排完啦, 左端和右端相等了(或交错了),注意呼应qs函数最后一行 (*第一行*)
int i = l - 1, j = r + 1, mid = q[(l + r) >> 1];
while(i < j){
do i++; while(q[i] < mid); // 循环完指针i停在第一个比mid大的数上,(或者等于,但不影响)
do j--; while(q[j] > mid);
if (i < j) swap(q[i], q[j]); // 指针交错时,交换。
}
qs(q, l, j), qs(q, j + 1, r); // 这里改了左右端点。即:【快排换完一次,切成两半后,继续在两个子区间继续快排】,直到... 见qs端第一行注释
}
int main(){
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%d", &nums[i]); // 读入
qs(nums, 0, n); // 整段快排
printf("%d", nums[k]); // 把题意要的(第k位)输出出来
return 0;
}