NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 28 题

完善程序：

（找第 $k$ 大的数） 给定一个长度为 $10^6$ 的无序正整数序列, 以及另一个数 $n (1\leq n\leq 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 [         ⑥           ]        

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

快速选择：选主元、左右扫描归位、判断递归区间。

②③条件写<=或>=会死循环；④主元赋值写错位置；⑤⑥递归区间反了。

考点：快速选择（Quick Select）｜partition分治

程序在做什么

随机选主元并交换到left，通过左右扫描将小于主元的放左边、大于主元的放右边，最后根据主元位置i与目标n的大小关系决定递归方向。