《线性时间选择实验报告》由会员分享，可在线阅读，更多相关《线性时间选择实验报告（4页珍藏版）》请在装配图网上搜索。
1、线性时间选择一. 实验目的：1. 理解算法设计的基本步骤和各步的主要内容、基本要求；2. 加深对递归设计方法基本思想的理解，并利用其解决现实生活中的问题；3. 通过本次试验初步掌握将算法转化为计算机上机程序的方法。二. 实验内容：1. 编写实现算法：给定n个元素，在这n个元素中找到第key小的元素；2. 将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包 括结果和具体的运行时间；3. 对实验结果进行分析。三. 实验操作：1. 线性时间选择的思想：首先将这n个元素分成5组，利用排序算法找到其中的中位数，再将这些中位数 排序找到整个数组的中位数median，以这个中位数med
2、ian为界限，将整个数组划分 为三部分，小于median，等于median和大于median三部分，判断key在哪部分中， 对那部分进行递归调用，直到找到等于key的元素为止。综上判断，其时间复杂度为：T(n)=high) return;int first=low;int last=high;int key=Listfirst;while(firstlast)(while(first=key) -last;Listfirst=Listlast;while(firstlast&Listfirst=key) +first;Listlast=Listfirst;Listfirst=key;quick
3、Sort(List,low,first-1);quickSort(List,last+1,high);3. 实验数据的输入：为了保证实验数据的随机性，本实验采用随机生成的方式提供数据，并将输入 输出数据存储到指定的文本文件中，需要采用C+文件流操作，对于数据的输入， 由于cin对数据的读取会忽略空格和换行操作，故使用cin流来控制数据的输入。输入代码实现：int write()(ofstream outFile;outFile.open(E:/程序设计/practice 1/算法设计与分析/文本文件夹/线性选择数据.txt”,ios:trunc);if(!outFile.is_open() c
4、outoutFile cant open!endl;cout输入随机数的范围：startend;cout输入要查找的数据个数：length;len=length;int* Array=new intlength;for(int i=0;ilength;i+)Arrayi=rand()%(end-start)+start;if(i=0) continue;for(;ji;j+)(while(Arrayi=Arrayj)(Arrayi=rand()%(end-start)+start;j=0;j=0;for(int i=0;ilength;i+) outFileArrayi;outFile.clo
5、se();return length;输出代码实现：int* read(int length)(ifstream inFile;inFile.open(E:/程序设计/practice 1/算法设计与分析/文本文件 夹/线性选择数据.txt);if(!inFile.is_open() coutinFile cant open!endl;int* Array=new intlength;int i=0;while(!inFile.eof()&iArrayi+;return Array;inFile.close();4.查找中位数：首先将所有的数据分成五组，找到每组中的中位数，再从找到的中位数中找
6、到整个 数组的中位数median，利用median将所有的数分成3份，小于median、等于median和大 于median三部分，判断所要找的元素在哪部分中，再将哪部分数据作为整体执行上述操 作，直到数组不能再分为止。代码实现：int grouping(int Array,int length,int key)( int i=0,start=0,group,m=0,n=0;group=length/5;if(group=0)(quickSort(Array,0,length-1);return Arraykey-1;else(int* List=new intgroup;int* Array
7、1=new intlength;int Array21;int* Array3=new intlength;while(group)(quickSort(Array,start,start+4);Listi=Arraystart+2;i+;start+=5;group-;quickSort(List,0,i-1);for(int j=0;jlength;j+)(if(ArrayjListi/2) Array3n+=Arrayj;if(Arrayj=Listi/2) Array20=Arrayj;if(m+1=key) return grouping(Array1,m,key);else return grouping(Array3,n,key-m-1);四.实验数据分析：本次实验采用随机数生成的算法提供数据，故可以提供大量的数据，下面是多次实 验数据的汇总。其中该时间是在查询第500个数据时统计的时间。苗制时行运数据查询时间图表5 15 0 L 0五.实验感受：在实验的测试中，当实验的数据偏大时，会出现溢出的现象，需要对代码中的数组 大小进行扩展，而且会出现程序卡住的现象，需要等待时间。
线性时间选择实验报告
