0001 template <typename T> void quickSelect ( Vector<T> & A, Rank k ) { //基于快速划分的k选取算法 0002 for ( Rank lo = 0, hi = A.size() - 1; lo < hi; ) { 0003 Rank i = lo, j = hi; T pivot = A[lo]; 0004 while ( i < j ) { //O(hi - lo + 1) = O(n) 0005 while ( ( i < j ) && ( pivot <= A[j] ) ) j--; A[i] = A[j]; 0006 while ( ( i < j ) && ( A[i] <= pivot ) ) i++; A[j] = A[i]; 0007 } //assert: i == j 0008 A[i] = pivot; 0009 if ( k <= i ) hi = i - 1; 0010 if ( i <= k ) lo = i + 1; 0011 } //A[k] is now a pivot 0012 }