0001 template <typename T> //通过调整元素位置，构造出区间[lo, hi)内的一个轴点
0002 Rank Vector<T>::partition( Rank lo, Rank hi ) { // DUP版：可优化处理多个关键码雷同的退化情况
0003    swap( _elem[lo], _elem[lo + rand() % ( hi - lo )] ); //任选一个元素与首元素交换
0004    T pivot = _elem[lo]; //经以上交换，等效于随机选取候选轴点
0005    while ( lo < hi ) { //从两端交替扫描，直至相遇
0006       do hi--; while ( ( lo < hi ) && ( pivot <  _elem[hi] ) ); //向左拓展后缀G
0007       if ( lo < hi ) _elem[lo] = _elem[hi]; //阻挡者归入前缀L
0008       do lo++; while ( ( lo < hi ) && ( _elem[lo] <  pivot ) ); //向右拓展前缀L
0009       if ( lo < hi ) _elem[hi] = _elem[lo]; //阻挡者归入后缀G
0010    } //assert: quit with lo == hi or hi + 1
0011    _elem[hi] = pivot; //候选轴点置于前缀、后缀之间，它便名副其实
0012    return hi; //返回轴点的秩
0013 }