算法实验报告——线性时间选择问题.doc

《算法实验报告——线性时间选择问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验五线性时间选择问题年级16学号20161101072姓名陈飞宇成绩专业信息安全实验地点C1-413指导教师陈丽萍实验日期一、实验目的1、理解分治法的基本思想2、掌握分治法解决问题的基本步骤，并能进行分治算法时间空间复杂度分析。二、实验内容线性时间选择问题：给定线性序集中n个元素和一个整数k（k>=1而且k<=n），要求在线性时间内找出这n个元素中第k小的元素。1.随机快速排序2.利用中位数线性时间选择三、算法描述1.随机快速排序在算法Randomized_Select中执行Randomized_Partition，将数组分成两个子数组

2、，在Randomized_Partition中调用Partition函数确定一个基准元素，对数组进行划分。由于划分是随机产生的，由此导致算法Randomized_Select也是一个随机化算法。2.利用中位数线性时间选择四、程序1.随机快速排序#include#include#includeintRandomized_Select(inta[],intp,intr,inti);intRandomized_Partition(inta[],intp,intr);intPartition(i

3、nta[],intp,intr);voidswap(int*a,int*b);intRandom(intp,intq);intmain(){inta[]={10,9,8,7,6,5,4,3,2,1};inti=3;..printf("第%d小的数是:%d",i,Randomized_Select(a,0,9,i));return0;}voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}intRandom(intp,intq)//产生p和q之间的一个随机整数{inti,number;s

4、rand((unsigned)time(NULL));number=rand()%(q-p+1)+p;returnnumber;}intPartition(inta[],intp,intr)//快排的部分{intx=a[r];inti=p-1;intj;for(j=p;j<=r-1;j++){if(a[j]<=x){i=i+1;swap(&a[j],&a[i]);}}swap(&a[i+1],&a[r]);returni+1;}intRandomized_Partition(inta[],intp,intr)//随机交换数字{inti=Ra

5、ndom(p,r);swap(&a[r],&a[i]);..returnPartition(a,p,r);}intRandomized_Select(inta[],intp,intr,inti)//选择算法核心{if(p==r)returna[p];intq=Randomized_Partition(a,p,r);intk=q-p+1;if(i==k)//如果刚好等于i，输出returna[q];elseif(i

6、元素在高区returnRandomized_Select(a,q+1,r,i-k);//因为a[q]已经是前面第k个小的，所以在后面就是i-k小}2.利用中位数线性时间选择#include#include#include#includeusingnamespacestd;templatevoidSwap(Type&x,Type&y);inlineintRandom(intx,inty);templatevoidBubbleSo

7、rt(Typea[],intp,intr);templateintPartition(Typea[],intp,intr,Typex);templateTypeSelect(Typea[],intp,intr,intk);intmain()..{//初始化数组inta[10];//必须放在循环体外面srand((unsigned)time(0));for(inti=0;i<10;i++){a[i]=Random(0,50);cout<<"a["<

8、endl;cout<<"第3小元素是"<