算法分析与设计实验报告
第 8次实验

姓名 学号 班级
时间 12.26下午 地点 四合院
实验名称
Sherwood 型线性时间选择算法

实验目的 1）通过上机实验，要求掌握 Sherwood 型线性时间选择算法的问题描述、算法设计思想、程序设计。
实验原理
使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，
并计算出程序运行所需要的时间
给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若 数
组为奇数个则输出中值，若数组为偶数个则输出第 n/2 小元素）。

实验步骤
① 先判断是否需要进行随机划分即（kϵ（1，n）?n>1?）；
② 产生随机数 j，选择划分基准，将 a[j]与 a[l]交换；
③ 以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组
值大于基准值；
④ 判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组
重复步骤②③④。

关键代码
template
inline void Swap(Type &a,Type &b) {
Type temp = a;
a = b;
b = temp;
}

//计算a[l:r]中第k小元素
template
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] 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-j+l-1;//右侧：k-(j-l+1)=k-j+l-1
l = j + 1;
}
else {
r = j - 1;
}
}
}

//计算a[0:n-1]中第k小元素
//假设a[n]是一个键值无穷大的元素
template
Type select(Type a[],int n,int k) {
if(k<1 || k>n) {
cout<<"请输入正确的k!"< return 0;
}
return select(a,0,n-1,k);
}
附录：完整代码

#include
using namespace std;

//随机数类
const unsigned long maxshort=66536L;
const unsigned long multiplier=1194211693L;

测试结果
实验心得
通过这次实验，我回顾了舍伍德线性时间查找问题
本次实验实现起来的代码较长，但在之前的实验中都要求使用舍伍德产生
随机数，因此本次实验还是比较简单的。主要是掌握对随机数RandomNuber类
的理解。在实现书上代码后，我将代码改进为随机产生序列的方式，手动选择
查找的数组元素（从小到大排序后）的序号，并输出到屏幕。因此，要想找出
最大元素，直接输入查找序号为数组大小即可得，同理最小元素为序号一，因
此可以实现最值求解。
通过本次实验发现，尽管嗯多时候实验的算法内容能在书本上找到，但是
如果能加入自己的理解进行修改代码，也会有很大的收获，因为只有掌握了思
想才能进行修改。
实验得分 助教签名
const unsigned long adder=12345L;
class RandomNumber{
private:
//当前种子
unsigned long randSeed;
public:
RandomNumber (unsigned long s=0); //构造函数，默认值0表示由系统自动
产生种子
unsigned short Random(unsigned long n); //产生0：n-1之间的随机整数
double fRandom(void); //产生[0，1）之间的随机实数
};

RandomNumber::RandomNumber(unsigned long s){
if(s==0) randSeed=time(0);
else randSeed=s;
}

unsigned short RandomNumber::Random(unsigned long n){
randSeed=multiplier*randSeed+adder;
return(unsigned short)((randSeed>16)%n);
}

double RandomNumber::fRandom(void){
return Random(maxshort)/double(maxshort);
}

template
inline void Swap(Type &a,Type &b) {
Type temp = a;
a = b;
b = temp;
}

//计算a[l:r]中第k小元素
template
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] 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-j+l-1;//右侧：k-(j-l+1)=k-j+l-1
l = j + 1;
}
else {
r = j - 1;
}
}
}

//计算a[0:n-1]中第k小元素
//假设a[n]是一个键值无穷大的元素
template
Type select(Type a[],int n,int k) {
if(k<1 || k>n) {
cout<<"请输入正确的k!"< return 0;
}
return select(a,0,n-1,k);
}

int main() {
int a[100] ={0};
int m,k;
cout<<"请输入数组元素个数； ";
cin>>m;
cout<<"请输入需要查找第几个元素： ";
cin>>k;
srand(time(0));
cout<<"\n原数组为："< for(int i=0; i a[i]=rand()%100;
cout< }
cout< cout<<"所给数组第"< return 0;
}