0001 template <typename T> void quickSelect( Vector<T>& A, Rank k ) { //基于快速划分的k选取算法
0002    for ( Rank lo = 0, hi = A.size(); lo < hi; ) {
0003       Rank i = lo, j = hi; T pivot = A[lo]; //大胆猜测
0004       while ( i < j ) { //小心求证：O(hi - lo + 1) = O(n)
0005          do j--; while ( ( i < j ) && ( pivot <= A[j] ) );
0006          if ( i < j ) A[i] = A[j];
0007          do i++; while ( ( i < j ) && ( A[i] <= pivot ) );
0008          if ( i < j ) A[j] = A[i];
0009       } // assert: quit with i == j or j+1
0010       A[j] = pivot; // A[0,j) <= A[j] <= A(j, n)
0011       if ( k <= j ) hi = j; //suffix trimmed
0012       if ( i <= k ) lo = i; //prefix trimmed
0013    } //A[k] is now a pivot
0014 }