找第 𝑘大的数

给定一个长度为 ${10}^6$的无序正整数序列, 以及另一个数 𝑛(1≤𝑛≤${10}^6$), 然后以类似快速排序的方法找到序列中第 𝑛大的数（关于第 𝑛 大的数：例如序列 {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;
    int m = 1000000;
    for (i = 1;i <= m;i ++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1,m,n);
    cout << a[ans];
    return 0;
}

1. ①处应填（ ）{{ select(1) }}

• a[left]
• a[tmp]
• a[right]
• a[n]

2. ②处应填（ ）{{ select(2) }}

• a[j]<value
• a[j]>value
• a[j]<a[i]
• a[j]>a[i]

3. ③处应填（ ）{{ select(3) }}

• a[i]<value
• a[i]>value
• a[i]<a[j]
• a[i]>a[j]

4. ④处应填（ ）{{ select(4) }}

• a[i]=a[left];
• a[i]=a[right];
• a[i]=a[tmp];
• a[i]=value;

5. ⑤处应填（ ）{{ select(5) }}

• i,right,n
• i+1,m,n
• i+1,right,n
• i,m,n

6. ⑥处应填（ ）{{ select(6) }}

• FindKth(1,i-1,n);
• FindKth(left,i-1,n);
• FindKth(1,i,n);
• FindKth(left,i,n);