线性时间选择中位数.docx
《线性时间选择中位数.docx》由会员分享，可在线阅读，更多相关《线性时间选择中位数.docx（6页珍藏版）》请在冰点文库上搜索。
线性时间选择中位数
湖南涉外经济学院计算机科学与技术专业
《算法设计与分析》课程
线性时间选择（中位数）
实验报告
班级：
学号：
姓名：
教师：
成绩：
2012年5月
【实验目的】
1掌握线性时间选择的基本算法及其应用
2利用线性时间选择算法找出数组的第k小的数
3分析实验结果，总结算法的时间和空间复杂度
【系统环境】
Windows7旗舰版平台
【实验工具】
VC++6.0英文企业版
【问题描述】
描述：
随机生成一个长度为n的数组。
数组为随机生成，k由用户输入。
在随机生成的自然数数组元素找出这n个数的第k小的元素。
例：
A[5]={3,20,50,10,21}k=3,则在数组A中第3小的元素为20
【实验原理】
原理：
将所有的数（n个），以每5个划分为一组，共[n/5]组（将不足五个的那组忽略）；然后用任意一种排序算法（因为只对五个数进行排序，所以任取一种排序法就可以了，这里我选用冒泡排序），将每组中的元素排好序再分别取每组的中位数，得到[n/5]个中位数；再取这[n/5]个中位数的中位数（如果n/5是偶数，就找它的2个中位数中较大的一个）作为划分基准，将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。
在这种情况下，找出的基准x至少比3（n-5）/10个元素大，因为在每一组中有2个元素小于本组的中位数，中位数处于1/2*[n/5-1]，即n/5个中位数中又有（n-5）/10个小于基准x。
同理，基准x也至少比3（n-5）/10个元素小。
而当n≥75时，3（n-5）/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。
思路：
如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍（0<ε<1是某个正常数），那么就可以在最坏情况下用O（n）时间完成选择任务。
例如：
若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。
所以，在最坏情况下，算法所需的
计算时间T（n）满足递归式T（n）≤T（9n/10）+O（n）。
由此可得T（n）=O（n）。
方法：
利用函数的相互调用和函数的递归调用实现程序的最终实现，一个主函数，三个子函数。
在主函数中只是单独的调用中位数算法的select函数，然后以select为入口进行调用bubble排序函数和partition划分函数。
【源程序代码】
#include
#include
#include
usingnamespacestd;
#defineMAX_VALUE100
#definerandom（）rand（）%MAX_VALUE
#defineN10
#defineMIDDLE5
inta[N];
classFind
{
public:
//冒泡排序
voidbubble（intfirst,intend）
{
for（inti=first;ifor（intj=end;j>i;j--）
if（a[j]{
swap（a[j],a[j-1]）;
}}
//数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边
intpartition（intp,intr,intx）
{
inti=p-1,j=r+1;
while
（1）
{
while（a[++i]while（a[--j]>x）;
if（i>=j）
break;
swap（a[i],a[j]）;
}
returnj-1;
}
//寻找中位数
intselect（intp,intr,intk）
{
if（r-p<75）
{
bubble（p,r）;
returna[p+k-1];
}
for（inti=0;i<（r-p-4）/5;i++）
{
ints=p+5*i,t=s+4;
bubble（s,t）;
inttemp=a[p+i];
a[p+i]=a[s+2];
a[s+2]=temp;
}
//找中位数的中位数
intx=select（p,p+（r-p-4）/5,（r-p-4）/10）;
i=partition（p,r,x）;
intj=i-p+1;
if（k<=j）
returnselect（p,i,k）;
else
returnselect（i+1,r,k-j）;
}
};
intmain（）
{
srand（（int）time（NULL））;
for（intk=0;k{
a[k]=random（）;
cout<}
cout<Findf;
intn=MIDDLE;
cout<<"TheNo."<"<return0;
}
【实验结果】
运行结果图（k=5）：
运行结果图（k=4）：
实验结果分析：
通过上面的结果图可以证明程序可以得到正确的排序结果。
升级会员 