NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 27 题

（找第 $k$ 大的数）给定一个长度为 $10^6$ 的无序正整数序列，以及另一个数 $n (1\le n\le 10^6)$，接下来以类似快速排序的方法找到序列中第 $n$ 大的数（关于第 $n$ 大的数：例如序列 $\{1,2,3,4,5,6\}$ 中第 $3$ 大的数是 $4$）。

#include <iostream>
using namespace std;

int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
    int c;
    c = a; a = b;    b = c;
}

int FindKth(int left, int right, int n)
{
    int tmp,value,i,j;
    if (left == right) return left;
    tmp = rand()% (right - left) + left;
    swap(a[tmp],a[left]);
    value =       ①         
    i = left;
    j = right;
    while (i < j)
    {
        while (i < j &&       ②       ) j --;
        if (i < j) {a[i] = a[j]; i ++;} else break;
        while (i < j &&        ③        ) i ++;
        if (i < j) {a[j] = a[i]; j --;} else break;
    }
        ④         
    if (i < n) return  FindKth(     ⑤      );
    if (i > n) return      ⑥                    
    return i;
}

int main()
{
    int i;
   

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考快速选择（Quickselect）找第k大。拿到题先看题目要第n大，记住大数放左边，基准选在a[left]，然后按这个方向写双指针划分，最后根据i和n的大小决定往哪边递归。

最容易把比较符号写反，比如以为第n大应该用a[j]>=value，其实大数要留在左边，所以从右往左找的是<=value的；或者基准值没取a[left]。还有递归边界容易搞混，i<n时第n大在右边要加1，i>n时在左边要减1，很多人会漏掉这个偏移。

这道题考查的是快速选择算法（Quickselect），它是快速排序的一个变体，专门用来在无序数组中查找第k大的元素。核心思想是：随机选一个基准值，把数组划分成“大于基准的放左边，小于基准的放右边”，然后根据基准最终的位置i和我们要找的第n大之间的关系，决定只在左边或右边继续递归，这样平均时间复杂度是O(n)。题目给的代码就是标准的Quickselect实现，只是留了几个空让你填。我先讲整体思路，再逐个空推演。拿到题先想：要找第n大，那大的数肯定在左边，小的在右边。所以划分的时候，从右向左找应该跳过比基准小的数（a[j]<=value），从左向右找应该跳过比基准大的数（a[i]>=value）。基准值本身要放在中间，也就是a[i]=value。最后看i和n的大小：如果i<n，说明第n大在右边，递归时要从i+1开始；如果i>n，说明在左边，递归时要到i-1结束；如果i==n，直接返回i。下面按代码顺序填空。第一个空①是基准值，代码里刚把随机选的a[tmp]换到了a[left]，所以基准就是a[left]。第二个空②是从右向左扫描，要找的是比基准小的数，所以条件是a[j]<=value。第三个空③是从左向右扫描，要找的是比基准大的数，所以条件是a[i]>=value。第四个空④是基准归位，扫描结束后i指向第一个小于基准的位置，把基准值放回去就是a[i]=value。第五个空⑤是i<n时的递归调用，第n大在右边，区间从i+1到right，参数是i+1,right,n。第六个空⑥是i>n时的递归调用，第n大在左边，区间从left到i-1，参数是FindKth(left,i-1,n)。把这些填进去，代码就完整了。关于易错点，除了刚才说的比较符号，很多人会忘记基准归位这一步，或者递归时没加偏移，那样就会越界或者找不到答案。考频方面，一维数组在题库里考了224题，覆盖从GESP五级到NOIP提高组初赛等9个级别，2023年突然爆到27题，2024年48题，2025年55题，2026年59题，说明数组基础越来越重要；快速排序相关考了53题，其中2024年15题、2025年14题、2026年7题，明显在往分治和排序结合的方向出；分治算法79题，递归函数115题，历年分布都很均匀，但2024-2026这几年在GESP五级、六级、八级以及NOIP提高组初赛中频率都在上升。预测的话，基于这些数据，未来一两年内，找第k大/第k小、快速选择、以及结合递归的数组操作题大概率还会以填空题或选择题形式出现，尤其是GESP五级和六级、NOIP提高组初赛这些级别，可能会继续加大考查力度，题目难度也会随着年份递增而略有提升。暂无足够依据预测具体的年份和题量，但可以肯定的是，掌握Quickselect这种分治思想对应对这类题目非常关键。