0001 template <typename T> Rank quickSelect( T const * A, Rank n, Rank k ) { //基于快速划分的k选取算法
0002    Vector<Rank> R; for ( Rank k = 0; k < n; k++ ) R.insert(k); //使用索引向量，保持原序列的次序
0003    for ( Rank lo = 0, hi = n; lo < hi; ) { //反复做quickParititon
0004       Rank i = lo, j = hi; Rank pivot = R[lo]; //大胆猜测
0005       while ( i < j ) { //小心求证：O(hi - lo + 1) = O(n)
0006          do j--; while ( ( i < j ) && ( A[pivot] <= A[R[j]] ) );
0007          if ( i < j ) R[i] = R[j];
0008          do i++; while ( ( i < j ) && ( A[R[i]] <= A[pivot] ) );
0009          if ( i < j ) R[j] = R[i];
0010       } //assert: 退出时必有 i = j 或 i = j+1
0011       R[j] = pivot; //[0, R[j]) <= [R[j]] <= (R[j], n)
0012       if ( k <= j ) hi = j; //剪除后缀
0013       if ( i <= k ) lo = i; //剪除前缀
0014    }
0015    return R[k];
0016 }