0001 template <typename T> Rank quickSelect(const T* A, const Rank n, const Rank 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+1; //大胆猜测
0005       for (Rank i = mi; i < hi; i++) //小心求证：LGU版快速划分
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 (k < mi) hi = mi; //猜大了，则剪除后缀
0010       else if (k == mi) return R[mi]; //或早或迟，总能猜中
0011       else lo = mi+1; //猜小了，则剪除前缀
0012    } //for
0013 } //quickSelect