AcWing 786. 第k个数

前备知识 快速排序

快速选择算法

使用分治思想

快速排序排的每一趟，数轴的左边都会是 小于等于 基准数、右边都是 大于等于 基准数的。

左边元素的个数是 \(j - l + 1\), 如果 \(k ≤ j - l + 1\) 的话，那么说明第 \(k\) 小数在左边区间，下次递归的区间就是左边，否则就是右边。

直到 \(l = r\) 时返回 \(q_l\)。

算法时间复杂度

复杂度 \(O(n)\)

虽然快速排序的复杂度是 \(O(nlogn)\)，然而，与快速排序中的双向递归不同，快速选择算法只递归到一侧——它正在搜索的元素所在的一侧。

这将平均复杂度从 \(O(nlogn)\) 降低到 \(O(n)\)，当然，最坏的情况还是是 \(O(n^2)\)。

代码实现

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;

int a[N];

int quick_sort(int q[], int l, int r, int k)
{
    //同快速排序
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    if (l >= r)
    {
        return q[l];
    }
    while (i < j)
    {
        while (q[ ++ i] < x);
        while (q[ -- j] > x);
        if (i < j)
        {
            swap(q[i], q[j]);
        }
    }
    if (j - l + 1 >= k) //第k小数在左边区间
    {
        return quick_sort(q, l, j, k);
    }
    else //第k小数在右边区间
    {
        return quick_sort(q, j + 1, r, k - (j - l + 1));
    }
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    printf("%d", quick_sort(a, 1, n, k));
    return 0;
}