main.cpp

Vc++中的舎伍德算法实现线性时间选择算法

// Sherwoos.cpp : 定义控制台应用程序的入口点。
//

#include "ElementType.h"
#include "Random.h"
#include <stdio.h>
#include <iostream>
using namespace std;

#define N 10

//舍伍德(sherwood)概率算法进行线性时间选择。

//// a[] 已有的数据数组
////  l  选择的低位置
////  r  选择的高位
////  k  l 和 r之间的一个位置值
/////功能: 选择l和r之间的k位置的一个整数
template<class Type> 
Type select(Type a[], int l, int r, int k) 
{ 
	static RandomNumber rnd; 
	while(true)
	{ 
		if(l >= r) 
			return a[l]; 
		int i=l, j = l + rnd.Random( r - l + 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) 
			return pivot; 

		a[l] = a[j]; 
		a[j] = pivot; 
		if(j-l+1<k) 
		{ 
			k=k-j+l-1; 
			l=j+1; 
		} 
		else 
			r=j-1; 
	} 
} 

template <class Type> 
Type Select(Type a[], int n, int k) 
{ 
	if(k<1||k>n) 
		printf("%d OutOfBounds",k); 
	return select(a, 0, n-1, k); 
} 

//对其数组进行随机洗牌
template<class Type> 
void Shuffle(Type a[], int n) 
{ 
	static RandomNumber rnd; 
	for(int i = 1; i<n; i++)
	{ 
		int j = rnd.Random(n-i)+i; 
		Swap(a[i], a[j]);
	}
}


///程序需要首先输入10个数值，以待选择
int main(int argc, char* argv[])
{

	Type a[N];
	int  pos = 1;
	int	 i;
	printf("please input %d numbers:\n",N);
	for( i = 0 ; i < N ; i++)
	{
		cin>>a[i].value;
		a[i].position = i;
	}

	printf("please input need select position(0<=position<%d):\n",N);

	cin>>pos;

	Shuffle(a,N);
	
	printf("Affter Shuffle ,10 numbers's order:");
	for( i = 0 ; i < N ; i++)
	{
		cout<<a[i].value << " ";
	}
	cout<<endl;

	Type ret = Select(a,N,pos);

	printf("Affter Select, 10 numbers's order:");
	for( i = 0 ; i < N ; i++)
	{
		cout<<a[i].value << " ";
	}
	cout<<endl;

	cout<<"select result is "<<ret.value << "(position:" << ret.position +1<< ")"<<endl;
	return 0;
}