各种查找算法的性能比较测试(顺序查找、二分查找)

《各种查找算法的性能比较测试(顺序查找、二分查找)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析各种查找算法的性能测试目录摘要4第一章：简介（Introduction）51.1算法背景5第二章：算法定义（AlgorithmSpecification）52.1数据结构52.2顺序查找法的伪代码62.3二分查找（递归）法的伪代码62.4二分查找（非递归）法的伪代码7第三章：测试结果（TestingResults）93.1测试案例表93.2散点图10第四章：分析和讨论124.1顺序查找124.1.1基本原理124.2.2时间复杂度分析124.2.3优缺点124.2.4该进的方法134.2二分查找（递归与非递归）134.2.1基本

2、原理134.2.2时间复杂度分析144.2.3优缺点144.2.4改进的方法14附录：源代码（基于C语言的）16声明18摘要在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方

3、法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。关键字：顺序查找、二分查找（递归与非递归）第一章：简介（Introduction）1.1算法背景查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。在数据结构课程中，我们已经学过了几种查找算

4、法，比较有代表性的有顺序查找（蛮力查找），二分查找（采用分治技术），哈希查找（理论上来讲是最好的查找方法）。第二章：算法定义（AlgorithmSpecification）2.1数据结构三种查找都是以整形数组作为主要的数据结构，如Inta[n]。我们主要测试的是算法的性能，并不是仅仅对算法的查找，以数组作为主要的数据结构能满足实验的要求。2.2顺序查找法的伪代码算法：顺序查找法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.....An）。返回：寻找

5、出给定值。伪代码如下：intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合，n是数组中元素的个数（即查找表的长度），k是要查找的元素{i=n;//从后往前把表中的元素与要查找的元素进行比较while(i>0&&r[i]!=k)i--;returni;//i的值为0则没找到，为非0则i为要查找元素的位置}2.3二分查找（递归）法的伪代码算法：二分查找（递归）法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4

6、.....An）。返回：寻找出给定值。伪代码如下：intsearch(inta[],intn,intk)//查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素{Low=0,High=n-1;//选择查找的最大的范围Mid=(Low+High)/2;if((Low>=High)

7、

8、(n==-1))return-1;//数字-1表示没有结果elseif(a[Mid]==k)returnMid;//找到要查找的元素elseif(a[Mid]>g)return(search(a,Mid-1,g));//需要在左边的更小的范围内查找elser

9、eturn(search(a+Mid+1,n-Mid,g));//在右边的更大的范围内查找}2.4二分查找（非递归）法的伪代码算法：二分查找（非递归）法目的：在给定的集合（或者是多重集，允许多个元素具有相同的值）中找寻一个给定的值。前提：给定一给定一个集合（或多重集）（A1、A2、A3、A4.....An）。返回：寻找出给定值。伪代码如下：intBinarySearch(inta[],intn,intk)//查找表放在数组a中，n是查找表中元素的个数，k是待查找的元素。{Low=0;high=n-1;//置区间初值while(low

10、){mid=(low+high)/2;if(key==a[mid])returnmid;//查找成功elseif(key>a[i])low=middle+1;//在