0001 template <typename T> //轴点构造算法:通过调整元素位置构造区间[lo, hi)的轴点,并返回其秩 0002 Rank Vector<T>::partition ( Rank lo, Rank hi ) { //版本A:基本形式 0003 swap ( _elem[lo], _elem[ lo + rand() % ( hi - lo ) ] ); //任选一个元素与首元素交换 0004 hi--; T pivot = _elem[lo]; //以首元素为候选轴点——经以上交换,等效于随机选取 0005 while ( lo < hi ) { //从向量的两端交替地向中间扫描 0006 while ( ( lo < hi ) && ( pivot <= _elem[hi] ) ) //在不小于pivot的前提下 0007 hi--; //向左拓展右端子向量 0008 _elem[lo] = _elem[hi]; //小于pivot者归入左侧子序列 0009 while ( ( lo < hi ) && ( _elem[lo] <= pivot ) ) //在不大于pivot的前提下 0010 lo++; //向右拓展左端子向量 0011 _elem[hi] = _elem[lo]; //大于pivot者归入右侧子序列 0012 } //assert: lo == hi 0013 _elem[lo] = pivot; //将备份的轴点记录置于前、后子向量之间 0014 return lo; //返回轴点的秩 0015 }