0001 template <typename T> Rank quickSelect( T const * A, Rank n, Rank k ) { //基于快速划分的k选取算法
0002    Vector<Rank> R(n); for ( Rank i = 0; i < n; i++ ) R.insert(i); //使用索引向量，保持原序列的次序
0003    for ( Rank lo = 0, hi = n; ; ) { //反复做quickParititon
0004       swap( R[lo], R[lo + rand()%(hi-lo)] ); T pivot = A[R[lo]]; Rank mi = lo; //大胆猜测
0005       for ( Rank i = lo+1; i < hi; i++ ) //LGU版partition算法
0006          if ( A[R[i]] < pivot )
0007             swap( R[++mi], R[i] );
0008       swap( R[lo], R[mi] ); //[0,mi) < [mi] <= (mi, n)
0009       if ( mi < k ) lo = mi + 1; //猜小了，则剪除前缀
0010       else if ( k < mi ) hi = mi; //猜大了，则剪除后缀
0011       else return R[mi]; //或早或迟，总能猜中
0012    }
0013 }