【数据结构C++邓俊辉】Chapter12排序

交换”

• swap随机挑选pivot的操作，在一定程度上降低最坏情况出现的概率。【或者使用 “三者取中法” ：挑选3个，取中值】

template 
Rank Vector::partition (Rank lo, Rank hi) {
	swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]);  // 任选1个元素与首元素交换
	T pivot = _elem[lo];
	while (lo < hi) { // 从向量的两端交替地向中间扫描
		while ( (lo < hi) && (pivot <= _elem[hi]) )
			hi--;
		_elem[lo] = _elem[hi];
		while ( (lo < hi) && (pivot > _elem[hi]) )
			lo++;
		_elem[hi] = _elem[lo];
	}
	_elem[lo] = pivot;
	return lo;
}

• 应对退化：考查所有元素均重复的退化情况，【版本A】的做法是不断向左移动hi，直至条件【lo

template 
Rank Vector::partition (Rank lo, Rank hi) {
	swap(_elem[lo], _elem[lo + rand() % (hi - lo + 1)]);  // 任选1个元素与首元素交换
	T pivot = _elem[lo];
	while (lo < hi) { // 从向量的两端交替地向中间扫描
		while (lo < hi)
			if (pivot < _elem[hi])
				hi--;
			else {
				_elem[lo++] = _elem[hi];	
				break;
			}
		while (lo < hi)
			if (pivot > _elem[lo])
				lo++;
			else {
				_elem[hi--] = _elem[lo];	
				break;
			}
	}
	_elem[lo] = pivot;
	return lo;
}