算法1(快排模板)

时间复杂度O(n)

第一层：O(n)

第二层：由于只会递归分界点左边区间或者右边区间之一，区间长度期望是缩小一半的，所以第二层O($\frac{n}{2}$)

第三层:同上面的分析可知，O($\frac{n}{4}$)

所以时间复杂度等于$O(n + \frac{n}{2} + \frac{n}{4} + \cdots) = O(n (1 + \frac{1}{2} + \frac{1}{4} + \cdots))$

其中$(1 + \frac{1}{2} + \frac{1}{4} + \cdots)$为等比数列求和,小于2

所以时间复杂度约为O(2n) = O(n)

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n,k;
int q[N];

//quick_sort(int l,int r,int k)为区间[l,r]的第k小的数
int quick_sort(int l,int r,int k){
    // 前半部分和快排完全相同
    if(l == r) return q[l];
    int i = l - 1,j = r + 1,x = q[l];
    while(i < j){
        do i ++;while(q[i] < x);
        do j --;while(q[j] > x);
        if(i < j){
            swap(q[i],q[j]);
        }
    }
    // 求出 SL 的长度（分界点 - 左边界 + 1）
    int sl = j - l + 1;
    // 情况 A
    if(sl >= k) return quick_sort(l,j,k);
    // 情况 B
    else return quick_sort(j + 1,r,k - sl);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i ++){
        scanf("%d",&q[i]);
    }
    cout << quick_sort(0,n - 1,k) << endl;
    return 0;
}

算法2(sort)

时间复杂度o(n$\log$n)

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int q[N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i ++){
        scanf("%d",&q[i]);
    }
    sort(q,q+n);
    printf("%d",q[k-1]);
    return 0;
}