数据结构（Java语言版）（第2版）（微课版） 课件 第9、10章 查找、排序

数据结构（Java语言版）09查找【知识目标】

掌握查找的相关概念；

掌握顺序查找法、二分查找法的算法原理及程序实现；

理解二叉排序树法的应用及平衡二叉排序树的实现过程；

掌握哈希查找法的原理；

掌握哈希函数构造方式及冲突解决方法。【能力目标】

能够进行无序表的顺序查找；

能够进行有序表的折半查找；

能够进行哈希表的快速查找。实例引入查找是指在给定的由同一数据类型构成的整体范围（如一篇文章、一个数据库等）内，寻找用户需要的数据的过程。若满足条件的数据存在，则查找成功，否则查找失败。查找的过程要依据用于识别某元素的字段，该字段可唯一识别数据元素，称其为查找关键字。查找的方法主要有顺序查找法、二分查找法（折半查找法）、二叉排序树法、哈希查找法等。查找的概念与方法顺序查找法算法描述将序列A用数组表示，将数字X和序列A中的每个元素进行比较，若相等，则表示X在序列A中存在，查找成功，否则查找失败。顺序查找法publicclassOrderSearch{publicvoidsearch(inta[],intx){inti=0;while(i<=a.length-1&&a[i]!=x)i++;if(i>=a.length)System.out.println("查找失败！");elseSystem.out.println("查找成功！");}publicstaticvoidmain(String[]args){int[]b={12,25,6,95,76,55,124,32,9,73};OrderSearchc1=newOrderSearch();c1.search(b,25);}}算法分析顺序查找法算法复杂度与序列表的长度有直接关系，若查找成功，则比较次数小于或者等于n；若查找不成功，则查找的次数永远为n。顺序查找法的时间复杂度为O(n)，n为序列中元素的个数。在n比较小，或者所查找的元素比较靠前时，顺序查找法较优。顺序查找法适用于查找表无序的情况。折半查找法算法描述

首先将待查找数据与被查找的有序序列的中间元素进行比较，若相等，则查找成功，并确定查找数据的位置；若不相等，则将被查找的有序序列分成两部分，并确定待查找的数据可能在哪一部分，在确定的部分中继续进行折半查找……重复以上折半查找操作，直至查找成功，或无数据可查找则失败。

折半查找法每次将被查找序列分成两部分，又称为二分查找法，其前提是被查找的序列必须是有序的。publicclassHalfSearch{publicintBinary_Search(inta[],intk){intlow,high,mid,pos=0;low=0;high=a.length-1;while(low<=high){mid=(low+high)/2;if(k<a[mid])high=mid-1;elseif(k>a[mid])low=mid+1;elsereturnmid;}}publicstaticvoidmain(String[]args){int[]b={6,9,12,25,32,55,73,76,95,124};HalfSearchc1=newHalfSearch();System.out.println(c1.Binary_Search(b,25));}}折半查找法算法分析

折半查找法的算法分析比较复杂，对于有序序列来说，每次范围减少一半，该算法比顺序查找算法要优一些，其时间复杂度为O(log2n)。折半查找法适用于有序序列。。二叉排序树法算法描述对于给定的序列A={55,25,6,95,76,12,124,32,9,73}，建立二叉排序树并完成查找过程。（1）建立二叉排序树根据二叉排序树性质，将第一个元素作为根节点，将其余元素和根节点比较，若比它小，则进入左子树，否则进入右子树，依次类推，完成二叉排序树的建立。二叉排序树法算法描述对于给定的序列A={55,25,6,95,76,12,124,32,9,73}，建立二叉排序树并完成查找过程。二叉排序树法（2）查找过程在按照前面过程所建立的二叉排序树中，欲查找X=95是否在这个序列中，即判断这两个数据是否在上述的二叉排序树中出现，其过程如下。对于X=95的情况：将X=95和根节点比较（95>55），查找在右子树中进行；将X=95和右子树根节点比较（95=95），查找成功。publicclassBinTreeSearch{publicvoidBinTree_Search(BinTreeNode3root,intx){if(root==null){System.out.println("查找失败："+x);return;}if(x>root.getData()){BinTree_Search(root.getRight(),x);}elseif(x<root.getData()){BinTree_Search(root.getLeft(),x);}else{System.out.println("查找成功："+root.getData());return;}}publicstaticvoidmain(String[]args){BinTreeMainbm=newBinTreeMain();BinSearchTreetree=bm.createSortTree();bm.BinTree_Search(tree.getRoot(),32);bm.BinTree_Search(tree.getRoot(),73);}}二叉排序树法算法分析

对于利用二叉排序树法进行查找，其时间复杂度受二叉排序树的深度影响，假设给定序列为有序序列，则构造的二叉排序树只有左子树或者只有右子树，则该算法退化为顺序查找算法；而当给定序列构造的二叉排序树的左、右子树分布比较均匀时，每次查找可减少一半左右的节点数，则查找效率较高。

因此，建立均匀的二叉排序树是提高此算法效率的重要因素。哈希查找法算法描述

哈希函数的构造方法在哈希查找法中作用非常大，将直接影响数据与存储地址之间的关系，同时也会影响查找的效率。下面介绍常用哈希函数的构造方法。哈希查找法1．直接法直接法是关键字的一个简单哈希函数，该函数在关键字和存储地址之间建立一一对应关系。对于关键字序列

A={1,5,9,13,17,…,81}，建立哈希函数，可在关键字和存储地址之间建立一个线性函数，即公式y=k·x+d，可以得到y=4·x+1。其中x是存储地址，y是关键字序列对应的值。通过直接法可在关键字和存储地址之间建立关系，利用对应关系，一次就可得知查找是成功还是失败。直接法对建立对应关系的关键字要求比较高，因此，可用直接法的关键字序列比较少。哈希查找法2．余数法余数法是针对数值型序列进行哈希查找的有效方法，其主要思路是针对给出的有序序列，通过求序列值的余数进行存储地址（或数组下标）的分配。利用公式y=xmodp

实现余数法哈希函数的构造。序号123456789关键字24151931227311039对应关系y=xmod11余数2483159106数组下标012345678910关键字

12243152739

193110当求得的余数相同时，在分配存储地址时就会出现将多个数据放到同一存储地址的现象，称该现象为哈希查找的冲突现象。哈希查找中的冲突现象是普遍存在的，需要合理解决该冲突，才能有效地使用哈希查找法处理查找问题。哈希冲突（1）顺序查找法顺序查找法是指当该存储地址已有数据元素存在时，就按照某种原则寻找其他空闲的存储地址，直到将所有元素存放位置全部确定为止。（2）链表法链表法解决冲突的思想是将发生冲突的记录构成一个链，都连接在以该记录为头节点的链表中，这样，既实现了地址的分配，同时还保留了记录的关键字与存储地址之间的对应关系。哈希冲突序列A={24,15,18,3,12,27,29,10,45}，当利用余数法建立关键字与存储地址之间的关系后，出现的冲突，对其采用链表法解决冲突后所得到的结果。假设一个班级有40名学生，根据某一学期的成绩，将其划分为5档，即90分以上、80分～90分、70分～80分、60分～70分、60分以下，且每个分数段的学生人数分别为3、7、11、14、5，对于某分数，查找是否有学生得此分数并给出得此分数的学生的人数。分析：可先确定其分数段（用折半法），然后在内部进行查找。将所有学生成绩按照分数段分成若干组，先在这些组之间建立相应的索引表，该索引表应该是有序的。查找时先确定某学生的成绩在哪个组内，然后在组内实现查找。例题classFindScore{intcount=0;int[][]score=newint[5][];publicFindScore(){score[0]=newint[]{98,90,95};score[1]=newint[]{87,82,88,89,85,84,80};score[2]=newint[]{76,75,74,72,73,71,79,77,70,75,70};score[3]=newint[]{61,63,67,68,69,60,65,65,64,63,62,68,69,64};score[4]=newint[]{45,34,23,34,54};}privateintfindScore(ints){intg=getGroup(s);int[]sc=score[g];intcount=0;for(inti=0;i<sc.length;i++){if(sc[i]==s){count++;}}returncount;}

例题intgetGroup(intx){intlow,high,mid,flag=0;low=0;high=4;x=9-x/10; //变换x便于查找分组if(x<0)x=0;if(x>4)x=4;while(low<=high){ //查找x所在分组mid=(low+high)/2;if(x<mid)high=mid-1;elseif(x>mid)low=mid+1;else{flag=mid;break;}}returnflag; //返回x所在分组的索引}

例题publicstaticvoidmain(String[]args){FindScorefs=newFindScore();inti=fs.findScore(68);if(i>0)System.out.println("共有"+i+"个学生得此分数！");elseSystem.out.println("没有学生得此分数！");}}例题结束！！数据结构（Java语言版）10排序【知识目标】²

掌握插入排序中直接插入排序和希尔排序的思想及实现；²

掌握交换排序中冒泡排序和快速排序的思想及实现；²

掌握选择排序中直接选择排序和堆排序方法的思想及实现；²

掌握归并排序的思想及实现；²

理解基数排序的思想及实现。【能力目标】²

具备熟练利用各种排序方法编写相应程序代码的能力；²

能够针对不同的应用选用合适的排序算法解决实际应用问题；²

具有比较各种排序方法、分析其算法的时间复杂度及空间复杂度的能力。实例引入学号姓名数学语文历史地理体育英语政治总分1王学亮788987899085866042彭飞907067758086955633李丽878078868595835944张月梦676698859032865245李雪菲988983838675876016王佳佳907762868585835687田悦悦855690958090825788张亮739089979082926139张雪燕7887878575758056710李飞89678889807683572排序：对于需要整理的文件或者相关数据，使之按某个类别的数据元素（或者数据项）的递增或递减次序排列起来的过程。记录：在排序中对应的数据元素被称为“记录”（或称为“元素”），记录可以由单个数据构成，也可以由一组数据构成，记录的集合称为“文件”（或称为“序列”），有时在内存中的文件也常被称为“表”。排序的概念关键字：对于由n个记录构成的序列{R1,R2,…,Rn}，其中Ki为排序时所依据的数据项，称其为关键字，关键字序列可记为{K1,K2,…,Kn}。排序还可以描述成对于需要整理的文件或者相关数据，使其在关键字关系Ki1≤Ki2≤…≤Kin（或者Ki1≥Ki2≥…≥Kin）下得到序列（Ri1,Ri2,…,Rin）的过程。排序的概念按照存储交换分类可将排序划分为内部排序和外部排序。排序按照内部排序的过程分类，可划分为4类，即插入排序、交换排序、选择排序，以及其他排序。排序按照稳定性分类可划分为稳定排序和不稳定排序。排序的分类插入排序-直接插入排序直接插入排序是指每次将一个记录插入已经排好序的序列中，直到结束为止。【基本思想】设1≤i≤n，已知文件或者相关数据中的记录{R1,R2,…,Ri−1}已经是按照关键字K1≤K2≤…≤Ki−1（或者K1≥K2≥…≥Ki−1）排成的一个有序序列，现将下一个待排序记录Ri插入{R1,R2,…,Ri−1}中，使其仍然满足有序的过程，就是插入排序。算法publicvoidinsertSort(int[]a) {intt;for(inti=1;i<a.length;i++){t=a[i];intj=i-1;while(j>=0){ //为每个待插入元素寻找插入位置if(t<a[j]) //发现插入位置后，执行元素移动a[j+1]=a[j]; //移动元素else //如果a[i]>a[j]，则退出内循环break;j--;}a[j+1]=t; //将待插入元素放到合适的位置}}算法分析

直接插入排序的实现是通过对记录比较和移动的方式进行的，其算法的时间复杂度为O(n2)，n为数据个数。当待排序的数据量非常大时，其算法的时间复杂度也比较高。希尔排序算法描述先将待排序记录分成若干个组，在每个组内进行直接插入排序，然后将划分的组逐步变大直到包含全部记录为止。其过程如下：①取一个小于序列记录个数n的整数d1作为第一个增量，把全部数据分成若干组，将所有距离为dl倍数的数据分在同一个组中。先在各组内进行直接插入排序；②取第二个增量d2<d1，重复上述分组和排序；③直至所取的增量di=1（di<di-l<…<d2<d1），即将所有数据放在同一组中进行直接插入排序。希尔排序publicvoidshellOne(Comparable[]a,intd){

intt;

intn=a.length;

intj=0;

for(inti=d;i<n;i++){ //对每组子序列执行插入操作if(a[i].compareTo(a[i-d])<0){t=a[i];j=i-d;do{ //查找a[i]的插入位置a[j+d]=a[j]; //后移记录j=j-d; //查找下一个记录}while(j>0&&pareTo(a[j])<0);a[j+d]=t; //将a[i]放到正确的位置上}

}}

publicvoidshellSort(Comparable[]a){

intincr=a.length;

do{incr=incr/2; //求下一增量，在这里增量通过除以2获得shellOne(a,incr); //一次增量为incr的希尔排序

}while(incr>=1);}算法分析

希尔排序的执行时间取决于增量序列，希尔排序增量序列的选择具有如下共同的特征：①最后一个增量必须为1，增量的取值一般不取2的倍数或者整数次幂的形式；②应该尽量避免序列中的值（尤其是相邻的值）互为倍数的情况；③希尔排序的性能分析过程比较复杂，经过大量实验得出，其算法的时间复杂度为O(n3/2)。。交换排序-冒泡排序算法描述冒泡排序是一种简单的交换排序，其排序过程：对相邻的记录按关键字进行大小比较，如果满足排序要求，则不进行交换，否则将两个记录交换。publicvoidbubble(Comparable[]a){Comparablet; //交换时使用的临时变量intn=a.length; //获取记录个数booleanflag; //flag标记是否有交换发生for(inti=1;i<n-1;i++){ //n个记录最多需进行n-1次排序flag=false; //假设没有发生交换for(intj=0;j<=n–i;j++){ //执行冒泡排序if(a[j].compareTo(a[j+1])>0){ //调用比较方法进行比较t=a[j]; //交换记录位置a[j]=a[j+1];a[j+1]=t;flag=true;}}if(!flag){ //如果没有发生交换，排序结束break;}}}冒泡排序算法分析冒泡排序是一种基于相邻元素之间位置交换的排序方法，是一种稳定的排序方法。其算法的时间复杂度与待排序序列的初始状态有直接关系，其平均时间复杂度为O(n2)，n为待排序元素的个数。快速排序

快速排序（QuickSort）是另一种交换排序，又称为分区交换排序，是对冒泡排序的改进。【基本思想（以升序为例）】在待排序的n个记录中任取一个记录（一般取第一个记录），以该记录作为排序的枢轴记录，将所有记录分为两组（这两组内部一般都是无序的），对于比枢轴记录关键字的值小或者相等的记录，将其放在枢轴记录的左边一组，对于比枢轴记录关键字大的记录放在枢轴记录的右边一组，称此为一次快速排序，对得到的两组记录分别重复上述的操作，直到完成整个排序过程。快速排序publicvoidquick(Comparable[]c,intstart,intend){Comparabletmp=c[start]; //暂存枢轴记录intn=end-start+1; //参与排序的记录个数inti=start,j=end;while(i<j){while(c[j].compareTo(tmp)>0&&i<j){ //从j开始搜索小于枢轴记录关键字的值j--;}if(i<j){ //出现小于枢轴记录关键字的值后，将j对应的值放到i位置处c[i]=c[j];i++;}while(c[i].compareTo(tmp)<=0&&i<j){//从i向后搜索，找出大于枢轴记录关键字的值i++;}if(i<j){ //出现大于枢轴记录关键字的值后，将i处的值放入j处c[j]=c[i];j--;}}c[i]=tmp; //完成一次搜索后，把枢轴记录值放在合适位置if(start<i–1)quick(c,start,i-1); //递归调用，对左子序列进行快速排序if(end>i+1)quick(c,i+1,end); //递归调用，对右子序列进行快速排序}快速排序算法分析

从快速排序算法程度的递归过程可知，快速排序的次数取决于递归的深度。最好的情况下，算法时间复杂度为O(nlog2n)；最坏情况下，快速排序的速度退化到简单排序水平，算法的时间复杂度为O(n2)。快速排序的特点：①记录的非顺序移动导致排序不稳定；②快速排序适用于顺序结构；③当记录数较大时，在一般情况下快速排序是内部排序方法中速度最快的一种。选择排序基本思想：对待排序序列{a1,a2,…,an}进行n次选择操作，其中第i次操作是选择第i个关键字较小（或较大）的记录，并将其放在第i个（或(n-i+1)个）记录的位置上，该排序通过比较选择需要交换的记录，对其进行记录位置的交换。选择排序包括直接选择排序和堆排序。直接选择排序基本思想：对于具有n个记录的待排序序列，以升序为例，其直接选择排序的步骤如下：①从待排序序列中，找到关键字值最小的记录；②如果关键字值最小的记录不是第一个，把关键字值最小的记录与第一个记录交换；③从余下的(n-1)个记录中，找出关键字值最小的记录与第二个记录交换，重复步骤①、②，直到排序结束。直接选择排序经过(n-1)次排序后将得到整个序列的有序序列。publicvoidselectSort(Comparable[]c) {Comparablemin,t; //最小记录临时存储变量minintmIndex=0; //记录最小记录的当前位置索引

intn=c.length;for(inti=0;i<n;i++){ //n个记录进行n-1次排序

min=c[i]; //假设第i个记录为最小记录并暂存

mIndex=i;for(intj=i+1;j<n;j++){ //在之后的记录中查找最小记录

if(c[j].compareTo(min)<0){min=c[j];mIndex=j;}}if(mIndex