线性时间选择实验报告

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

1、线性时间选择一．实验目的：1.理解算法设计的基本步骤和各步的主要内容、基本要求；2.加深对递归设计方法基本思想的理解，并利用其解决现实生活中的问题；3.通过本次试验初步掌握将算法转化为计算机上机程序的方法。二．实验内容：1.编写实现算法：给定n个元素，在这n个元素中找到第key小的元素；2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间；3.对实验结果进行分析。三．实验操作：1.线性时间选择的思想：首先将这n个元素分成5组，利用排序算法找到其中的中位数，再将这些中位数排序找到整个数组的中位数median，以这个中

2、位数median为界限，将整个数组划分为三部分，小于median，等于median和大于median三部分，判断key在哪部分中，对那部分进行递归调用，直到找到等于key的元素为止。综上判断，其时间复杂度为：T(n)<=cn（n为实验数据的个数），故为线性时间。2.快速排序：本次排序使用的是快速排序，快速排序是一种相对较快的排序方式，能够减少一定的时间开销。代码实现：voidquickSort(intList[],intlow,inthigh){if(low>=high)return;intfirst=low;intlast=high;intkey=List[

3、first];while(first=key)--last;List[first]=List[last];while(first

4、文本文件中，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，故使用cin流来控制数据的输入。3

5、4输入代码实现：intwrite(){ofstreamoutFile;outFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt",ios::trunc);if(!outFile.is_open())cout<<"outFilecan'topen!"<

6、>start>>end;cout<<"输入要查找的数据个数："<>length;len=length;int*Array=newint[length];for(inti=0;i

7、ay[i]<<"";outFile.close();returnlength;}输出代码实现：int*read(intlength){ifstreaminFile;inFile.open("E://程序设计/practice1/算法设计与分析/文本文件夹/线性选择数据.txt");if(!inFile.is_open())cout<<"inFilecan'topen!"<>Array[i++];returnArr

8、ay;inFile.close();}4.查找中位数：首先将所有的数据分成五组，找到每组中的中位数，再从找到的中位数中找到整个数组的中位数median，利用median将所有的数分成3份，小于median、等于median和大于median三部分，判断所要找的元素在哪部分中，再将哪部分数据作为整体执行上3

9、4述操作，直到数组不能再分为止。代码实现：intgrouping(intArray[],intlength,intkey){inti=0,start=0,group,m=0,n=0;group=length/5;if(group==0){quickSort(

10、Array,0,length-1);r