资源描述：
《外文翻译《整理与查询算法集》_译文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、毕业论文(设计)文献翻译本翻译源自于：SortingandSearchingAlgorithms:ACookbook毕业设计名称：手机归属地查询算法研究外文翻译名称：分类与查询算法大全学生姓名：陈文平院(系)：电信学院专业班级：信工10702指导教师：严碧波辅导教师：严碧波时间：2011-2-21至2011-06-10排序与查询算法手册ThomasNiemann著，陈文平译1.介绍数组和链表是用于存储信息的两个基本数据结构。我们可能希望搜索，插入或者删除数据库中基于一个关键字的记录。这个章节检查在数组和链表上的一些操作的执行情况。数组图1-1表示一
2、个数组，七个元素长，包含数字值。为了继续搜索数组，我们可以使用图1-2中的算法。比较的最大数目是7，并且搜索的关键字重现时在A[6]中。图1-1一个数组图1-2按次序搜索图1-3二进制搜索如果数据是分类的，一个二进制搜索可以被使用（图1-3）。变量Lb和Ub分别保持对较低界限和较高界限的数组的跟踪。我们从数组中的中间元素开始检查。如果正在搜索的关键元素小于中间那个元素，则她一定是在数组的上半部分。因此，我们将Ub放置在(M-1)处。通过这种方式限制了我们的下一个迭代循环到顶部的一半的数组。用这种方法,每步迭代半数组的大小被搜查。例如,第一个迭代会离
3、开3项测试。第二个迭代后,将会有一项左考验的。因此,它只需要三个迭代才能找到任何号码。这是一种有力的方法。给定含1023个元素的数组，我们能在一次比较中将搜索范围缩小至511个元素。再进行一次比较后，我们只看255个元素。事实上，我们搜索整个数组仅需10次比较。除了搜寻的时候,我们可能会希望插入或删除数据。不幸的是，一个数组不能很好的安排这些操作。例如，插入数字18到图1-1中，我们需要将A[3]…A[6]向下移动一个空位。然后再复制18到A[3]中。一个类似的问题在删除数字时也会发生。为了提高插入和删除操作的效率，链表可以被使用。链表图1-4一个
4、链表在图1-4我们有相同的数据存储在一个链表。假如指针X和P在图中显示，则数字18可能如下方式被插入：X->Next=p->Next;p->Next=X;使用链表进行插入和删除操作是非常有效的。你也许会惊讶怎么指针p被放置在了第一个位置。当然，我们不得不做顺序搜索来找到插入点X。虽然我们提高了插入或删除的性能，但它这样做事在牺牲搜索时间。定时估计有好几种算法可以用来比较算法的性能。一种方法是简单的为各个算法做几个试验，并且比较定时。另一种发放是评估所需的时间。例如，我们可以指定搜索时间为O(n)。2、排序这里给出了几种算法,包括插入排序、希尔排序和
5、快速排序法。插入是最简单的方法,不需要任何额外的存储空间。外壳排序是在插入的基础上进行了一个简单的改造,显著的提高了算法的性能。可能是最有效的最流行的方法就是快速排序法,是因为这种方法针对大型阵列有很高的效率。2．1插入排序其中一个最简单的方法是一种排序数组插入排序。例如日常生活中我们打牌的时候，插入序列排序就会出现。解决这个问题就是您提取手中牌里的一张卡片,转移剩余的卡片,并将提取的卡片,放在合适的地方。这个过程将重复进行,直到所有的卡片都是按照正确的顺序排列。平均最坏的时候就会进行O(n^2)次。原理在阵列的顶端开始,例如在图2-1(a)、提取
6、3。那么以上元素转移下来,直到我们找到正确的位置插入3。这个过程重复在图2-1(b)与下一个数字。最后,在图2-1(c),我们完成这一排序把2插入在合适的地方。图2–1插入排序假设在数组中存在n个元素:将数组中,我们必须索引n–1个条目。对每个条目时,我们可能需要审查和转移n-1个其他的索引条目,导致一个O(n^2)的算法。插入排序是一种归位的排序。也就是说,我们对数组进行了归位分类。所以不需要额外的存储器。插入排序的也是一种稳定的排序法。在输入数据且出现相同的关键字时，稳定排序就会记住原始序列。实现源插入分类排序算法可以在文件ins.c中找到。只
7、需要将TypedefT算子和比较算子compGT改一改,就可以将数据反映并存储表格中。2.2希尔排序法尔排序法,是DonaldL自行研制开发的。希尔算法是一种非稳定的非原地排序的算法。希尔算法因为它在插入排序的基础上能迅速地移动值而大大的提高了排序的效率。平均排序时间是O(n1.25),而最坏的时间是O(n1.5)。原理在图2-2(1)我们需要插入排序的一个例子。首先我们提取1、移位3和5到下一槽,然后插入1，相当于移位两次。在接下来的框架,在两次移位的条件下我们能插入2。这个过程会一直持续,直到最后一个框架,在那里,一共有2+2+1=5转变已经有
8、所成就。在图2-2(b)的一个例子说明了壳类。首先,我们在做一个插入排序使用间距为二。在第一帧我们检验编号的3倍。提取一个
