《C语言程序设计与数据结构》课件第15章

C语言程序设计与数据结构第15章查找与排序C语言程序设计与数据结构总体要求：掌握查找与排序的基本概念；掌握顺序查找和二分查找的算法；掌握直接插入排序、简单选择排序、冒泡排序的算法；学习重点：查找的有关算法：顺序查找、折半查找；常用的排序方法：插入排序、交换排序。C语言程序设计与数据结构主要内容15.1基本概念15.2查找算法介绍15.3排序算法介绍15.4典型习题分析解答C语言程序设计与数据结构15.1基本概念15.1.1查找的基本概念查找表(SearchTable)是由同一类型的数据元素(或记录)构成的集合。若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(StaticSearchTable)。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(DynamicSearchTable)。本章集中讨论静态查找表。所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。关键字(Key)是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(PrimaryKey)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(SecondaryKey)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找(Searching)根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。C语言程序设计与数据结构15.1.2排序的基本概念排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。假设含n个记录的序列为{R1，R2，…，Rn}，若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。C语言程序设计与数据结构15.2查找算法介绍15.2.1顺序查找顺序查找(SequentialSearch)的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。此查找过程可用下列算法描述。【算法15.1】顺序查找的算法：intSearch_Seq(SqlistST，KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。ST.r[0].key=key;//0号单元作为监视哨for(i=ST.length;!EQ(ST.r[i].key,key);--i);//从后往前找returni；//找不到时，i为0}//EndofSearch_Seq查找操作的性能分析:C语言程序设计与数据结构15.2.2折半查找折半查找(BinarySearch)的查找过程是：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。(具体查找过程见第7章)算法如下：//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。【算法15.2】折半查找的算法：intbinsrch(SqlistL,intkey){intmid,low,high,find;low=1;high=L.length;find=0;/*置区间初值*/while((low=high)&&(!find)){mid=(low+high)/2;/*求中点*/if(k==L.r[mid].key)find=1;/*已查到*/elseif(kL.r[mid].key)low=mid+1;/*在后半区间查找*/elsehigh=mid-1;/*在前半区间查找*/}if(find)return(mid);/*查找成功，返回找到元素的位置*/elsereturn(0);/*查找不成功，返回0标记*/}//Search_BinC语言程序设计与数据结构折半查找的平均查找长度是:ASL=log2(n+1)-1可见，折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构(对线性链表无法进行折半查找)。以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有斐波那契查找和插值查找。C语言程序设计与数据结构15.2.3分块查找分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在处理线性表时，如果既希望能够快速查找，又要经常动态变化，则可以采用分块查找方法。分块查找又称索引顺序查找，要求将待查的元素均匀的分成块，块间按大小排序，块内不排序。因此需要建立一个块的最大（或最小）关键字表，称之为“索引表”。具体而言，假设我们按结点元素关键字升序方式组织表中各块，则要求第一块中任一结点的关键字值都小于第二块中所有结点的关键字值；第二块中任一结点的关键字值都小于第三块中所有结点的关键字值；如此类推。然后选择每块中的最大（或最小）关键字值组成索引表。换言之，索引表中的结点个数等于线性表被分割的块数。C语言程序设计与数据结构例如要找关键字为k的元素，则先用折半查找法由索引表查出k所在的块，再用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元素，则先由索引表查出41在第二块中（294164），再在第二块中找到41。由此我们可以总结：分块查找分两步进行，第一步确定要查找结点在表中的哪一块，第二步在确定的块中找到该结点。分块查找的平均查找长度为：ASL=ASLb+ASLe其中ASLb是折半查找的平均查找长度，ASLe是用顺序查找法查块内元素的平均查找长度。设每块中有s个元素，可以近似的得到：可以看出分块查找的平均查找长度位于顺序查找和折半查找之间。下面我们简单的对以上几种查找方法做出比较：（1）平均查找长度：折半查找最小，分块查找次之，顺序查找最大；（2）表的结构：顺序查找对有序表、无序表均适用；折半查找仅适用于有序表；分块查找要求表中元素是逐段有序的，就是块与块之间的记录按关键字有序；（3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了查找效率。C语言程序设计与数据结构15.3排序算法介绍15.3.1插入排序15.3.1.1直接插入排序直接插人排序(StraightInsertionSort)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。（具体过程见第七章数组）【算法15.3】直接插入排序的算法：voidinsertSort(Sqlist&L)//对顺序表L作直接插入排序。{for(i=2；i=L.1ength；++i)if(L.r[i].keyL.r[i-1].key){//“”，需将L.r[i]插入有序子表L.r[0]=L.r[i]//复制为哨兵for(j=i-1;(L.r[0].keyL.r[j].key);--j)L.r[j+1]=L.r[j]；//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}//insertsortC语言程序设计与数据结构直接插入排序的算法简洁，容易实现，那么它的效率如何呢?首先从空间角度来看，它只需要一个辅助空间r[0]。从时间耗费角度来看，主要时间耗费在关键词比较和移动元素上。对于一趟插入排序，算法中的while循环的次数主要取决于待插记录与前i-1个记录的关键词的关系上。最好情况为(顺序)r[i].keyr[i-1].key，while循环只执行1次，且不移动记录；最坏情况为(逆序)r[i].keyr[1].key，则while循环中关键词比较次数和移动记录的次数为i-1。对整个排序过程而言，最好情况是待排序记录本身已按关键词有序排列，此时总的比较次数为n-1次，移动记录的次数也达到最小值2(n-1)(每一次只对待插记录r[i]移动两次)；最坏情况是待排序记录按关键词逆序排列，此时总的比较次数达到最大值为，即，记录移动的次数也达到最大值，即。算法执行的时间耗费主要取决于资料的分布情况。若待排序记录是随机的，即待排序记录可能出现的各种排列的概率相同，则可以取上述最小值和最大值的平均值，约为。因此，直接插入排序的时间复杂度为T(n)=O(n2)，空间复杂度为S(n)=O(1)。C语言程序设计与数据结构15.3.1.2希尔排序基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。排序过程：先将整个待排序记录以d1为步长分成若干子序列，把所有相隔为d1的记录放在同一组内；在每个分组内进行直接插入排序；在将整个待排序记录序列以d2(d2d1n)为步长重新分组和在每组内进行直接插入排序；重复上步，直至dt=1，即所有记录放进一个组中进行直接插入排序。另外，对间隔数d的取法也很多，通常的取法可以是(i=2,3,4,…)式中，n为序列中元素的总个数。C语言程序设计与数据结构【算法15.4】希尔排序的算法：voidShellInsert(Sqlist&L，intdk){/*一趟增量为dk的插入排序，dk为步长因子*/inti,j;for(i=dk+1；i=L.length；i++)if(L.r[i].keyL.r[i-dk].key)/*小于时，需elem[i]将插入有序表*/{L.r[0]=L.r[i]；/*为统一算法设置监测*/for(j=i-dk；j0&&L.r[0].keyL.r[j].key；j=j-dk)L.r[j+dk]=L.r[j]；/*记录后移*/L.r[j+dk]=L.[0]；/*插入到正确位置*/}}voidShellSort(Sqlist&L，intdlta[]，intt){/*按增量序列dlta[0，1…，t-1]对顺序表*p作希尔排序*/intk;for(k=0；kt；k++)ShellSort(L，dlta[k])；/*一趟增量为dlta[k]的插入排序*/}C语言程序设计与数据结构为什么希尔排序的时间性能优于直接插入排序呢？直接插入排序在文件初态为正序时所需要时间最少，实际上，当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。另一面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在希尔排序时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序是不稳定的。C语言程序设计与数据结构15.3.2选择排序15.3.2.1直接选择排序基本思想：直接选择排序是一种简单的排序方法，它的基本步骤是：把顺序存储的n个待排序的记录看成由一个有序区和一个无序区组成。初始时，有序区为空，无序区为(R1,R2,……Rn)；在一趟选择排序中，从无序