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

实验五线性时间选择问题年级16学号20161101072姓名陈飞宇成绩专业信息安全实验地点C1-413指导教师陈丽萍实验日期一、实验目的1、理解分治法的基本思想2、掌握分治法解决问题的基本步骤，并能进行分治算法时间空间复杂度分析。二、实验内容线性时间选择问题：给定线性序集中n个元素和一个整数k（k=1而且k=n），要求在线性时间内找出这n个元素中第k小的元素。1.随机快速排序2.利用中位数线性时间选择三、算法描述1.随机快速排序在算法Randomized_Select中执行Randomized_Partition，将数组分成两个子数组，在Randomized_Partition中调用Partition函数确定一个基准元素，对数组进行划分。由于划分是随机产生的，由此导致算法Randomized_Select也是一个随机化算法。2.利用中位数线性时间选择四、程序1.随机快速排序#includestdio.h#includestdlib.h#includetime.hintRandomized_Select(inta[],intp,intr,inti);intRandomized_Partition(inta[],intp,intr);intPartition(inta[],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小的数是:\n%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;srand((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=Random(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(ik)//如果i比k小，证明要找的元素在低区returnRandomized_Select(a,p,q-1,i);else//找的元素在高区returnRandomized_Select(a,q+1,r,i-k);//因为a[q]已经是前面第k个小的，所以在后面就是i-k小}2.利用中位数线性时间选择#includestdio.h#includestdlib.h#includectime#includeiostreamusingnamespacestd;templateclassTypevoidSwap(Type&x,Type&y);inlineintRandom(intx,inty);templateclassTypevoidBubbleSort(Typea[],intp,intr);templateclassTypeintPartition(Typea[],intp,intr,Typex);templateclassTypeTypeSelect(Typea[],intp,intr,intk);intmain(){//初始化数组inta[10];//必须放在循环体外面srand((unsigned)time(0));for(inti=0;i10;i++){a[i]=Random(0,50);couta[i]:a[i];}coutendl;cout第3小元素是Select(a,0,9,3)endl;//重新排序，对比结果BubbleSort(a,0,9);for(inti=0;i10;i++){couta[i]:a[i];}coutendl;}templateclassTypevoidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){intran_num=rand()%(y-x)+x;returnran_num;}//冒泡排序templateclassTypevoidBubbleSort(Typea[],intp,intr){//记录一次遍历中是否有元素的交换boolexchange;for(inti=p;i=r-1;i++){exchange=false;for(intj=i+1;j=r;j++){if(a[j]a[j-1]){Swap(a[j],a[j-1]);exchange=true;}}//如果这次遍历没有元素的交换,那么排序结束if(false==exchange){break;}}}templateclassTypeintPartition(Typea[],intp,intr,Typex){inti=p-1,j=r+1;while(true){while(a[++i]x&&ir);while(a[--j]x);if(i=j){break;}Swap(a[i],a[j]);}returnj;}templateclassTypeTypeSelect(Typea[],intp,intr,intk){if(r-p75){BubbleSort(a,p,r);returna[p+k-1];}//(r-p-4)/5相当于n-5for(inti=0;i=(r-p-4)/5;i++){//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数BubbleSort(a,p+5*i,p+5*i+4);Swap(a[p+5*i+2],a[p+i]);}//找中位数的中位数Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x);intj=i-p+1;if(k=j){returnSelect(a,p,i,k);}else{returnSelect(a,i+1,r,k-j);}}五、测试与分析1.随机快速排序O(n)2.利用中位数线性时间选择O(n)