0001 template <typename T> //轴点构造算法:通过调整元素位置构造区间[lo, hi)的轴点,并返回其秩 0002 Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本C 0003 swap ( _elem[lo], _elem[ lo + rand() % ( hi - lo ) ] ); //任选一个元素与首元素交换 0004 T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换,等效于随机选取 0005 int 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 ( int 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 }