（NOIP2008）找第k大的数

给定一个长度为1000000的无序正整数序列，以及另一个数n(1<=n<=1000000)，接下来以类似快速排序的方法找到序列中第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;
    int m=1000000;
    for(i=1;i<=m;i++)
        cin>>a[i];
    cin>>n;
    ans=FindKth(1,m,n);
    cout<<a[ans];
    return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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