题目描述

递归,调用自身,让看得到出口.
分治,将1e5的大区间分割成多个小区间,当每个区间都满足,所有区间合并在一起也都满足.
要遍历所有区间,分段区间二分地遍历,时间复杂度最好情况下:O(NlogN);
最坏情况下O(NN),当要排序数组越有序,时间越复杂!

样例

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> pii;
int q[N];
void quick_sert(int l,int r)
{
    if(l >= r) return;
    int ll = l-1,rr = r+1,jianzhi = q[ll+rr >> 1];
    while(ll < rr) 
    {
        while(q[++ll] < jianzhi);
        while(q[--rr] > jianzhi);
        if(ll < rr) swap(q[ll],q[rr]);
    }
    quick_sert(l,rr),quick_sert(rr+1,r);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    int n,k; cin >>n >>k;
    for(int i = 0; i <n;i++) cin >> q[i];
    quick_sert(0,n-1);
    cout << q[k-1] << '\n';
    return 0;
}