0001 template <typename T> //轴点构造算法:通过调整元素位置构造区间[lo, hi)的轴点,并返回其秩 0002 Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本B:可优化处理多个关键码雷同的退化情况 0003 swap ( _elem[lo], _elem[ lo + rand() % ( hi - lo ) ] ); //任选一个元素与首元素交换 0004 hi--; T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换,等效于随机选取 0005 while ( lo < hi ) { //从向量的两端交替地向中间扫描 0006 while ( lo < hi ) 0007 if ( pivot < _elem[hi] ) //在大于pivot的前提下 0008 hi--; //向左拓展右端子向量 0009 else //直至遇到不大于pivot者 0010 { _elem[lo++] = _elem[hi]; break; } //将其归入左端子向量 0011 while ( lo < hi ) 0012 if ( _elem[lo] < pivot ) //在小于pivot的前提下 0013 lo++; //向右拓展左端子向量 0014 else //直至遇到不小于pivot者 0015 { _elem[hi--] = _elem[lo]; break; } //将其归入右端子向量 0016 } //assert: lo == hi 0017 _elem[lo] = pivot; //将备份的轴点记录置于前、后子向量之间 0018 return lo; //返回轴点的秩 0019 }