软件技术基础_姚全珠_第4章查找和排序(绝对免费!供大家学习).ppt

计算机软件基础,第四章查找与排序,计算机软件基础,4.1查找与排序概述4.2线性表上的查找4.3二叉树上的查找4.4哈希查找4.5直接插入排序4.6交换排序4.7选择排序4.8多关键字排序,本章内容,4.1查找与排序概述,1.与查找有关的概念,(1)查找：又称检索，是指在大量数据中寻找关键字值等于给定值的记录。(2)主关键字：指在组成记录的若干个数据项中，能够唯一标识一条记录的数据项。(3）次关键字：指在组成记录的若干个数据项中，不能唯一标识一条记录的数据项。,计算机软件基础,(4)平均查找长度(AverageSearchLength)指查找过程中，对于查找关键字进行比较的平均比较次数，记为ASL。其计算公式如下所示：其中，pi为查找第i个元素的概率，ci为查找第i个元素所需进行的比较次数。通常认为查找每个元素的概率相等，即p1=p2=pn=1/n。,计算机软件基础,注意！：本章所介绍的各种查找方法都是基于主关键字的查找。,2.与排序有关的概念,（1）排序：指将一组记录按照指定关键字大小递增（或递减）的次序排列起来。（2）稳定性：若待排序的一组记录中存在多个关键字值相同的记录，如果使用某种排序算法进行排序后，相同关键字值的多个记录的相对次序与排序前相比没有改变，则称此排序算法具有稳定性。,稳定性举例,计算机软件基础,4.2线性表的查找,假设后面算法涉及的线性表的类型定义如下（假设关键字类型为integer型）：structure/list/integerkeydatatypeotherendstructure,计算机软件基础,一.顺序查找,1基本思想从线性表的表尾到表头（从后往前），或者从线性表的表头到表尾（从前往后），依次将每个元素的关键字值和给定关键字值相比较，寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素，则查找成功；若查找完整个线性表都找不到满足条件的元素，则查找失败。,计算机软件基础,2算法描述functionseqsearch(r,x,n)*结构体类型list定义略integerseqsearch,xrecord/list/r(0:n)r(0).key=xi=ndowhile(r(i).key.ne.x)i=i-1enddoseqsearch=iend,3.算法说明在算法中，线性表中的元素存放于数组r的下标为1n的数组元素中，为了避免每次比较时都要判断条件（i0）以防数组下标越界，因此设置了数组元素r0充当“监视哨”。4.算法分析当查找成功时，若所查元素为r(n)，只需一次比较；若所查元素为r(1)，需要n次比较；若所查元素为r(i)，则需n-i+1次比较。因此在等概率条件下查找成功的平均查找长度为：,计算机软件基础,计算机软件基础,二.二分查找,1基本思想找到查找区间的中间位置，用此位置上元素的关键字值与待查关键字值相比较。若相等，则查找成功；否则，将查找范围缩小到半个区间，只在可能存在待查元素的前半区间或后半区间进行查找。重复上述过程，直到查找成功或查找范围缩小到空。,计算机软件基础,注意：！二分查找算法在使用时必须满足前面提到的两个前提条件：1.线性表中的元素必须按照查找关键字排列有序；2.线性表必须以顺序存储方式存储。,计算机软件基础,二分查找过程示例,下面是在一个升序线性表18，26，32，45，52，66，80，91上查找关键字为80的元素的二分查找过程。,计算机软件基础,2算法描述functionbinsearch(r,x,n)*结构体类型list定义略integerbinsearch,xrecord/list/r(n)integerlow,high,mid,flaglow=1high=nflag=0binsearch=0,do10while(low.le.high.and.flag.eq.0)mid=(low+high)/2if(x.eq.r(mid).key)thenbinsearch=midflag=1elseif(x.gt.r(mid).key)low=mid+1elsehigh=mid-1endif10continueend,计算机软件基础,3.算法说明算法中的整型变量low、high、mid分别用于标识查找区间的左端点、右端点及中间位置。在升序排列的线性表中，若待查元素关键字值小于中间位置元素的关键字值，则待查元素只可能出现在区间上半部，故缩小查找区间到原区间的上半部（区间左端点不变，区间右端点变为mid1）；若待查元素关键字值大于中间位置元素的关键字值，则待查元素只可能出现在区间下半部，故缩小查找区间到原区间的下半部（区间右端点不变，区间左端点变为mid+1）；若待查元素关键字值等于中间位置元素的关键字值，则查找成功，返回该元素的位置值mid。,计算机软件基础,二分查找过程可借助二叉树来描述。在这棵二叉树中，把查找区间中间位置元素的序号作为根结点，区间上半部和下半部元素的序号分别作为左、右子树中的结点，此树被称为二分查找判定树。二分查找过程例子所对应的判定树如下图所示。,4算法分析,计算机软件基础,显然，查找某个元素所需的比较次数正好是该元素序号在判定树中所处的层次数。对8个元素进行二分查找的平均查找长度为：ASL=（1+2+2+3+3+3+3+4)/8=2.6。,为了讨论方便，不妨假设二分查找判定树为一个满二叉树，此时该树的深度h为log2(n+1)，树中第k层上的结点个数为2k-1。因此，在等概率条件下，查找成功时的平均查找长度为：,结论：当n很大时，二分查找的平均查找长度可近似为log2(n+1)1。,计算机软件基础,三.分块查找,分块查找是性能介于顺序查找和二分查找之间的一种查找方法，又称索引顺序查找。,分块查找的使用前提：1.将线性表分块:将线性表均匀地分成若干块，块内元素不要求有序，但必须保证块间有序，即后一块中元素的关键字值均大于前一块元素的关键字值；2.建立索引表:建立由各块中最大关键字值和起始位置两个数据项构成的索引表ID。,计算机软件基础,例：若需对如下线性表进行分块查找，如何对其分块及建立索引表。,索引表ID,起始地址addr,1,6,11,最大关键字值key,23,48,86,计算机软件基础,1.基本思想首先在索引表中查找，确定待查元素所在的块；然后在所确定的那一块中查找指定关键字的元素。由于索引表是有序表，查找时可采用二分查找或顺序查找；而在块内查找时，由于块内无序，故只能采用顺序查找。,2.算法描述,略。,计算机软件基础,4算法分析,ASL=ASL索引表+ASL块内,若在索引表中采用二分查找，那么ASL为：ASLlog2(b+1)-1+(s+1)/2log2(n/s+1)+s/2若在索引表中采用顺序查找，那么ASL为：ASL=(b+1)/2+(s+1)/2=(s2+2s+n)/2s显然，分块查找的效率介于顺序查找和二分查找之间。,计算机软件基础,1.算法思想首先在整棵树中进行查找，用待查关键字值与根结点的关键字值相比较，若等于根结点的关键字值，则查找成功；若小于根结点的关键字值，则缩小查找范围到左子树；若大于根结点的关键字值，则缩小查找范围到右子树；在左、右子树中的查找与在整棵树中的查找过程相同。持续上述查找过程，直到找到或查找范围为空。,4.3二叉排序树的查找,计算机软件基础,2.算法分析分析：在二叉排序树上进行查找，若查找成功，实际上是从根结点出发走了一条从根到待查结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。结论：在二叉排序树上的查找过程中和关键字的比较次数不会超过树的深度，因此平均查找长度与树的形态（深度）有关。最坏的情况是当二叉排序树为一棵单支树的时候；最好的情况是二叉排序树为一棵平衡二叉树的时候。,计算机软件基础,4.4哈希查找,思考：分析前面介绍过的各种查找方法的共同点，考虑是否有突破常规的高效率查找方法？提示：在元素的存放位置上动动脑筋，使查找效率大大提高。,计算机软件基础,一.哈希表的概念及建立,1.哈希表的有关概念,（1）哈希函数哈希函数是指对于线性表中各个元素所建立的关键字值与其在一维数组中存放位置之间的函数（对应关系），其形式为：addr(ai)=H(ki)其中，H为哈希函数名，ai为线性表中的第i个元素，ki为第i个元素的关键字值。,计算机软件基础,（2）哈希地址通过哈希函数，对线性表中的每个元素根据其关键字值所计算出的在一维数组中的存放位置称为该元素的哈希地址。（3）哈希表按哈希地址存放每个元素所生成的顺序表称作哈希表。哈希表空间的单元数应大于元素的个数。,计算机软件基础,例：若有一线性表的关键字集合为65，47，86，34，12，77，对其构造的哈希函数为：H(k)=k/10，若所开辟的哈希表空间地址范围为09，则形成的哈希表如下所示：,思考：若还存在关键字为69的元素，在生成哈希表的过程中会有什么麻烦，有什么办法能解决？,计算机软件基础,（4）冲突在计算哈希地址时所出现的不同关键字对应到同一地址的现象，称为冲突。,处理冲突中的两个关键问题：1.如何构造合适的哈希函数以使冲突降低到最少程度；2.是如何在冲突出现时正确地处理冲突。,计算机软件基础,2哈希函数的构造方法（1）直接定址法取关键字值本身或其线性函数值作为哈希地址。其形式为：H(k)=ak+b，其中a和b为常数。（2）数字分析法取关键字中分布较均匀的n个数位作为哈希地址（n的值应为哈希表的地址位数）。,计算机软件基础,（3）平方取中法取关键字平方后的中间几位作为哈希地址，是对数字分析法的改进方法。（4）除留余数法取关键字被某个不大于哈希表表长m的数p除后所得的余数作为哈希地址，其形式为：H(k)=mod(k,p)。一般情况下，可以选p为不大于m的最大质数。,计算机软件基础,二.冲突的处理方法,1开放定址法基本思想：若在某个地址处发生了冲突，则沿着一个特定的探测序列在哈希表中探测下一个空单元，一旦找到，则将新元素存入此单元中。其探测的序列可用下式描述：Hi=mod(H(k)+di),m)（i=1，2，3，)（1）当di取1，2，3，,m1时，称为线性探测再散列；（2）当di取12，12，22，22，32，32，j2（jm/2）时，称为二次探测再散列。,计算机软件基础,2链地址法,基本思想：为每个哈希地址建立一个单链表，将所有哈希地址相同的元素存储在同一单链表中，单链表的头指针存放在基本表中。在将某个关键字的结点向单链表中插入时，既可以插在链尾上，也可以插在链头上。,计算机软件基础,例：设有关键字序列（62，30，18，45，21，78，66，32，54，48），现用除留余数法作为哈希函数，分别用线性探测再散列、二次探测再散列处理冲突、链地址法处理冲突，画出所生成的哈希表。,哈希地址表,计算机软件基础,计算机软件基础,链地址法处理冲突生成的哈希表,计算机软件基础,思考：一旦按照某种处理冲突的方法生成了哈希表，如何在此哈希表上实现指定关键字值元素的查找？,解决方法：哈希查找的过程实质上就是按照建立哈希表时处理冲突的方法，根据哈希地址在哈希表上查找指定关键字的元素。由于冲突的存在，在哈希查找过程中对关键字的比较次数可能不只一次。,计算机软件基础,三.哈希查找,算法前提：1.除留余数法作为哈希函数hash(k)=mod(k,p);2.用线性探测再散列处理冲突;3.哈希表已经建好（哈希表空间为0m-1）,算法：,计算机软件基础,算法：,functionhash(k)parameter(p=13)integerhashhash=mod(k,p)endfunctionhashsearch(ht,k)parameter(m=15)*结构体类型list定义略integerhashsearch,hash,i,hrecord/list/ht(0:m-1),计算机软件基础,h=hash(k)i=0do10while(i.lt.m.and.ht(h).key.ne.k)h=mod(h+1,m)i=i+110continueif(i.lt.m)thenhashsearch=helsehashsearch=-1endifend,计算机软件基础,4.5直接插入排序,一.基本思想将整个数据表（n个记录）看成是由无序表和有序表两个部分组成，初始状态时，有序表中仅有第一个记录，排序共需进行n-1趟，每趟排序时将无序表中的一个记录插入到有序表中的恰当位置，最终使整个数据表有序排列。,计算机软件基础,例：对于关键字序列38，20，46，38，74，91，12，25进行直接插入排序，写出排序过程中每趟排序的结果。,计算机软件基础,注：在关键字序列中存在两个相同的关键字38，因此在后面一个38的下面加下划线以示区别。,思考：直接插入排序算法的稳定性如何？,结论：插入排序算法具有稳定性。,分析：两个38排序前和排序后的相对次序没有发生变化。,计算机软件基础,二.算法描述,算法功能：实现将一个长度为n的线性表r上的所有元素按关键字升序排列。,subroutineinsertsort(r,n)record/list/r(0:n)*结构体类型list定义略do10i=2,nr(0)=r(i)j=i-1do20while(r(0).key.lt.r(j).key)r(j+1)=r(j)j=j-120continuer(j+1)=r(0)10continueend,计算机软件基础,设置r(0)的作用：1.用于保存待插记录r(i)的值，以免在后移过程中被覆盖而丢失；2.作为“监视哨”，防止数组下标越界。,直接插入排序算法的执行效率与数据表的初态有关。当数据表初态升序排列时效率最高，每趟排序都不执行内循环（不作记录后移），时间复杂度为O(n)；当数据表初态降序排列时效率最低，每趟排序都需进行i-1次（i为外循环控制变量）比较和后移，时间复杂度为O(n2)。经证明，直接插入排序算法具有稳定性，其平均时间复杂度为O(n2)。,三.算法分析,计算机软件基础,4.5交换排序,交换排序是通过对数据表中的记录进行两两比较，次序不符合要求就交换的方法实现数据表的有序排列。目前有两种较为常用的交换排序方法：冒泡排序和快速排序。本节重点介绍其中的冒泡排序方法。,计算机软件基础,4.5.1冒泡排序,一基本思想将n个记录看作按纵向排列，每趟排序时自下至上对每对相邻记录进行比较，若次序不符合要求（逆序）就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置，整个排序过程共进行n-1趟，依次将关键字最小、次小、第三小的各个记录“冒到”表的第一个、第二个、第三个位置上。,计算机软件基础,例：对于关键字序列38，20，46，38，74，91，12，25进行冒泡排序，写出排序过程中每趟排序的结果。第一趟排序的详细过程,计算机软件基础,二算法描述下面的冒泡排序算法实现将一个长度为n的线性表r上的所有元素按关键字升序排列。subroutinebubblesort(r,n)*结构体类型list定义略record/list/r(n),tempintegerflag,i,jflag=1i=1do10while(i.lt.n.and.flag.eq.1)flag=0do20j=n-1,i,-1,if(r(j+1).key.lt.r(j).key)thenflag=1temp=r(j)r(j)=r(j+1)r(j+1)=tempendif20continuei=i+110continueend,冒泡排序算法的执行效率与数据表的初态有关。当数据表初态升序排列时效率最高，排序只需进行一趟，时间复杂度为O(n)；当数据表初态降序排列时效率最低，需进行n-1趟排序且每次比较都要进行交换，时间复杂度为O(n2)。经证明，冒泡排序算法具有稳定性，其平均时间复杂度为O(n2)。,三.算法分析,4.6选择排序,选择排序是通过每一趟排序过程中从待排序记录中选择出关键字最小（大）的记录，将其依次放在数据表的最前或最后端的方法来实现整个数据表的有序排列。本节将介绍选择排序方法中最简单且最常用的简单选择排序。,一.基本思想第一趟排序在所有待排序的n个记录中选出关键字最小的记录，将它与数据表中的第一个记录交换位置，使关键字最小的记录处于数据表的最前端；第二趟在剩下的n-1个记录中再选出关键字最小的记录，将其与数据表中的第二个记录交换位置，使关键字次小的记录处于数据表的第二个位置；重复这样的操作，依次选出数据表中关键字第三小、第四小的元素，将它们分别换到数据表的第三、第四个位置上。排序共进行n-1趟，最终可实现数据表的升序排列。,计算机软件基础,例：对于关键字序列38，20，46，38，74，91，12，25进行简单选择排序，写出排序过程中每趟排序的结果。,二算法描述下面的简单选择排序实现将一个长度为n的线性表r上的所有元素按关键字升序排列。subroutineselectsort(r,n)*结构体类型list定义略record/list/r(n),tempdo10i=1,n-1k=ido20j=i+1,nif(r(j).key.lt.r(k).key)k=j20continueif(i.ne.k)thentemp=r(k)r(k)=r(i)r(i)=tempendif10continueend,简单选择排序算法中关键字的比较次数与数据表的初态无关。排序共进行n-1趟，在第i趟排序中总是需要进行n-i次比较。经证明，简单选择排序算法不具有稳定性，其平均时间复杂度为O(n2)。,三.算法分析,4.8多关键字排序,一.问题特点：1.排序关键字不止一个；2.排序关键字级别高低不同；3.人工方法的处理过程不便于在计算机上实现。,人工方法的处理过程在计算机上实现的主要难点：按不同关键字排序的记录个数不同。,人工方法的处理过程：按级别从高到低的次序对不同关键字进行排序。在排序过程中若发现有高关键字值相同的记录，再对这些记录按级别较低的关键字进行排序。,计算机处理方法的出发点：,为了便于算法在计算机上的实现，应该使按照不同关键字排序的对象都相同（整个线性表中的所有记录）。,计算机处理方法的实现难点：,1.排序关键字的顺序如何安排？2.怎样在高关键字相同时由低关键字的值决定记录的次序？,1.先按级别低的关键字进行排