线性时间选择实验报告

线性时间选择一. 实验目的：1. 理解算法设计的基本步骤和各步的主要内容、基本要求；2. 加深对递归设计方法基本思想的理解，并利用其解决现实生活中的问题；3. 通过本次试验初步掌握将算法转化为计算机上机程序的方法。二. 实验内容：1. 编写实现算法：给定n个元素，在这n个元素中找到第key小的元素；2. 将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包 括结果和具体的运行时间；3. 对实验结果进行分析。三. 实验操作：1. 线性时间选择的思想：首先将这n个元素分成5组，利用排序算法找到其中的中位数，再将这些中位数 排序找到整个数组的中位数median，以这个中位数median为界限，将整个数组划分 为三部分，小于median，等于median和大于median三部分，判断key在哪部分中， 对那部分进行递归调用，直到找到等于key的元素为止。综上判断，其时间复杂度为：T(n)<=cn (n为实验数据的个数)，故为线性时间。2. 快速排序：本次排序使用的是快速排序，快速排序是一种相对较快的排序方式，能够减少一 定的时间开销。代码实现：void quickSort(int List,int low,int high)(if(low>=high) return;int first=low;int last=high;int key=Listfirst;while(first<last)(while(first<last&&Listlast>=key) -last;Listfirst=Listlast;while(first<last&&Listfirst<=key) +first;Listlast=Listfirst;Listfirst=key;quickSort(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() cout<<"outFile can't open!"<<endl;cout<<"输入随机数的范围：<<endl;int length,len,start,end,j=0;cin>>start>>end;cout<<"输入要查找的数据个数："<<endl;cin>>length;len=length;int* Array=new intlength;for(int i=0;i<length;i+)Arrayi=rand()%(end-start)+start;if(i=0) continue;for(;j<i;j+)(while(Arrayi=Arrayj)(Arrayi=rand()%(end-start)+start;j=0;j=0;for(int i=0;i<length;i+) outFile<<Arrayi<<""outFile.close();return length;输出代码实现：int* read(int length)(ifstream inFile;inFile.open("E:/程序设计/practice 1/算法设计与分析/文本文件 夹/线性选择数据.txt");if(!inFile.is_open() cout<<"inFile can't open!"<<endl;int* Array=new intlength;int i=0;while(!inFile.eof()&&i<length) inFile>>Arrayi+;return Array;inFile.close();4.查找中位数：首先将所有的数据分成五组，找到每组中的中位数，再从找到的中位数中找到整个 数组的中位数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* Array1=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;j<length;j+)(if(Arrayj<Listi/2) Array1m+=Arrayj;if(Arrayj>Listi/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五.实验感受：在实验的测试中，当实验的数据偏大时，会出现溢出的现象，需要对代码中的数组 大小进行扩展，而且会出现程序卡住的现象，需要等待时间。