0001 template <typename T> //轴点构造算法：通过调整元素位置构造区间[lo, hi)的轴点，并返回其秩
0002 Rank Vector<T>::partition( Rank lo, Rank hi ) { // LGU版
0003    swap( _elem[lo], _elem[lo + rand() % ( hi - lo )] ); //任选一个元素与首元素交换
0004    T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换，等效于随机选取
0005    Rank mi = lo;
0006    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0007    //   ---- L < [lo] ----- ] ----- [lo] <= G --- ] [ ----- Unknown -------
0008    // X x . . . . . . . . . x . . . . . . . . . . . x . . . . . . . . . . x X
0009    // |                     |                       |                       |
0010    // lo (pivot candidate)  mi                      k                       hi
0011    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0012    for ( Rank k = lo + 1; k < hi; k++ ) //自左向右扫描
0013       if ( _elem[k] < pivot ) //若当前元素_elem[k]小于pivot，则
0014          swap( _elem[++mi], _elem[k] ); //将_elem[k]交换至原mi之后，使L子序列向右扩展
0015    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0016    //   --------- L < [lo] ---------- ] ------------- [lo] <= G ----------]
0017    // X x . . . . . . . . . . . . . . x . . . . . . . . . . . . . . . . . x X
0018    // |                               |                                     |
0019    // lo (pivot candidate)            mi                                    hi
0020    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0021    swap( _elem[lo], _elem[mi] ); //候选轴点归位
0022    return mi; //返回轴点的秩
0023 }