题目描述
给定一个长度为 $n$ 的整数数列,以及一个整数 $k$,请用快速选择算法求出数列从小到大排序后的第 $k$ 个数。
输入格式
第一行包含两个整数 $n$ 和 $k$。
第二行包含 $n$ 个整数(所有整数均在 $1 \sim 10^9$ 范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第 $k$ 小数。
数据范围
$1 \le n \le 100000$,
$1 \le k \le n$
输入样例:
5 3
2 4 1 5 3
输出样例:
3
算法
(暴力枚举) $O(n^2)$
write here…
时间复杂度
write here…
空间复杂度
write here…
C++ 代码
#include <bits/stdc++.h>
using namespace std;
void QuickSort(int* data,int low,int high)
{
if(low < high)
{
int pivot = data[(low+high)/2];
int i = low-1;
int j = high+1;
while (i < j)
{
do --j; while(data[j] > pivot && j > low);
do ++i; while(data[i] < pivot && i < high);
if(i < j)
swap(data[j],data[i]);
}
QuickSort(data,low,j);
QuickSort(data,j+1,high);
}
}