方法一、分界点两侧的个数判断

算法分析

基于快速选择排序算，但是又有点差异性，主要思想依然是三个部分：

1、找到分界点x，x 可以是a[l]，a[r]， a[l+r>>1]，当判定结束后，分界点的下标为 j

2、对于分界点 j 来说，左边所有的数 <x ，右边所有的数 >x

3、根据需要，求 第k大 数，记分界点左边有 llen = j - l + 1个数

​ a、当 $k \leq llen$ 时，递归排序 分界点左侧，quick_sort(a, l, j, k)

​ b、当 $k \geq llen$ 时，递归排序 分界点右侧，quick_sort(a, j+1, r, k-llen)

时间复杂度：

第一层的平均时间复杂度：$O(n)$

第二层的平均时间复杂度：$O(\frac{n}{2})$

第三层的平均时间复杂度：$O(\frac{n}{4})$

….

总的平均时间复杂度为：$\leq O(2n)$

模板

void quick_sort(int a[], int l, int r, int k)
{
    if (l==r) return a[l];
    int i = l-1, j = r+1, x = a[l+r>>1];
    while(i<j)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j) swap(a[i], a[j]);
    }
    if(k<=j) return quick_sort(a, l, r, k);
    return quick_sort(a, j+1, r, k);
}

完整代码

#include<iostream>
using namespace std;
int n, k, a[100005];

// C++ 局部变量和全局变量相同时，局部变量的优先级更高

int quick_sort(int a[], int l, int r, int k){
    if(l==r) return a[l];
    int i = l-1, j = r+1, x = a[(l+r)>>1];
    while(i<j)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j) swap(a[i], a[j]);
    }
    int llen = j- l + 1;
    if(k<=llen) return quick_sort(a, l ,j ,k);
    else return quick_sort(a, j+1, r, k-llen); 
}

int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<quick_sort(a, 1, n, k);
    return 0;
}

方法二、下标判断法

完整代码

#include<iostream>
using namespace std;
int n, k, a[100005];
// C++ 局部变量和全局变量相同时，局部变量的优先级更高

int quick_sort(int a[], int l, int r, int k){
    if(l==r) return a[l];
    int i = l-1, j = r+1, x = a[(l+r)>>1];
    while(i<j)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i<j) swap(a[i], a[j]);
    }
    if(k<=j) return quick_sort(a, l ,j ,k);
    else return quick_sort(a, j+1, r, k); 
}

int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<quick_sort(a, 1, n, k);
    return 0;
}