算法实验-Sherwood型线性时间选择问题

实验原理

希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有

这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。

对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要O(n^2)计算时间。舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。

关键代码

template<class Type>
Type select(Type a[], int l, int r, int k){
	while (true){
		if (l >= r){
			return a[l];
		}
		int i = l, j = l + rand() % (r - 1 + 1);//随机选择划分基准
		Swap(a[i], a[j]);
		j = r + 1;
		Type pivot = a[l];
		//以划分基准为轴做元素交换
		while (true){
			while (a[++i] < pivot);
			while (a[--j] > pivot);
			if (i >= j){
				break;
			}
			Swap(a[i], a[j]);
		}
		if (j - l + 1 == k){//第k小
			return pivot;
		}
		//a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大
		a[l] = a[j];
		a[j] = pivot;
		//对子数组重复划分过程
		if (j - l + 1 < k){
			k = k - j + l - 1;//右侧：k-(j-l+1)=k-j+l-1
			l = j + 1;
		}else{
			r = j - 1;
		}
	}
}
template <class Type>
inline void Swap(Type& a, Type& b){
	Type temp = a;
	a = b;
	b = temp;
}