计算机软件基础课件：查找与排序

常用的查找和排序方法《计算机软件基础》01.查找的概念02.常用的静态查找03.排序的概念主要内容05.排序方法应用举例04.常用的内部排序本章重点难点本章重点：三种查找和三种排序方法的基本思想和操作过程。本章难点：三种查找和三种排序方法的算法实现。查找和排序是数据处理过程的主要操作查找即在一个含有众多的数据元素（记录）集合中找出某个特定的数据元素。排序就是把一组数据元素（记录）按其关键字的某种次序排列起来，使其具有一定顺序，便于查找。查找和排序的方法很多，针对不同的数据结构，需要采用不同的查找和排序方法。01查找的概念1.查找的概念查找表是由同一类型的数据元素构成的集合。查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若查找表中存在这样一个记录，则为“查找成功”，其查找结果为：给出整个记录的信息，或指示该记录在查找表中的位置；否则为“查找失败”，其查找结果为空。对查找表进行的操作有以下四种:010203查询某个特定的数据元素是否在查找表中04检索某个特定的数据元素的各种属性在查找表中插入一个数据元素从查找表中删除某个数据元素静态查找表：若对查找表只做前两种操作，即只执行查找操作。动态查找表：若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。

02常用的静态查找1.设“监视哨”的顺序查找顺序查找是一种最基本、直接的查找方法。它从线性表的一端开始，向另一端逐个取出数据元素的关键字，并与要查找的关键字key进行比较，以判断是否存在要找的关键字。1）基本思想假设n个数据元素已存入一维数组a[1..n]的区域中，a[0]作为监视哨，存放要查找的关键字key。顺序查找的整个过程是从最后一个数据元素a[n]开始，向前依次与key比较，直至a[1]，若数据元素的值和key都不相等时，则返回0，查找失败；否则返回数据元素的下标位置，查找成功。2）算法流程与实现设低位监视哨的顺序查找流程#include<stdio.h>intsearch_seq(inta[],intkey,intn){inti=n;a[0]=key;

/*设“监视哨”*/while(a[i]!=key)/*从第n个元素到第1个依次找key*/i--;returni;}3）平均查找长度

2.折半查找

又称为二分查找，用于待查数据元素序列是采用顺序存储结构的有序表情况。1）基本思想假设待查序列按照数据元素的值升序排列，在查找时不必顺序进行比较，而是将待查关键字key先与“中间位置”数据元素的值比较，若相等，则查找成功。若key小于“中间位置”的数据元素值，则在有序表的前半部按上述方法进行查找；否则，在有序表的后半部按上述方法查找。2）算法流程与实现#include<stdio.h>intsearch_bin(inta[],intkey,intn){intlow,mid,hig;low=1;hig=n;while(low<=hig){ mid=(low+hig)/2;if(key==a[mid])returnmid;/*找到则返回位置序号*/elseif(key<a[mid])/*继续在前半区间范围查找*/hig=mid-1; elselow=mid+1;/*继续在后半区间范围查找*/}return0;}例10-1

已知待查序列为：2，5，9，13，18，26，32。待查关键字K分别为13、32和4，试写出折半查找过程。3)折半查找判定树

折半查找判定树中每个结点对应待查找序列的一个数据元素，结点值是该数据的下标序号，根结点是待查序列中间数据的下标位置序号mid，左子树为mid位置左边结点的下标位置序号，右子树为mid位置右边结点的下标位置序号。圈外数字是数据元素值;圈内数字是对应下标位置序号。待查找结点在判定树中的层数为折半查找成功的比较次数。

例10-2

试构造具有9个结点的折半查找判定树，并求查找成功的平均查找长度ASL。树的特点？？

3.二叉查找树查找1）二叉查找树定义一棵二叉查找树（又称二叉搜索树）是一棵二叉树，它可以为空。如果不为空，它将满足下列条件：根的非空左子树的所有结点的关键字小于根结点的关键字。根的非空右子树的所有结点的关键字大于根结点的关键字。左、右子树都是二叉查找树。2）二叉查找树上的查找由于二叉查找树的特殊性质，查找可以比较方便地实现。其过程如下：1）查找从树的根结点开始，如果树为空，返回NULL，表示未找到关键字为key的结点。2）查找树非空，则根结点关键字和key进行比较，依据比较结果，需要进行不同的处理：若根结点关键字小于key，则在此根结点的右子树中继续进行查找；若根结点关键字大于key，则在此根结点的左子树中继续进行查找；若两者比较结果是相等，查找完成，返回指向此结点的指针。3）构造二叉查找树的方法已知一个关键字序列，构造二叉查找树的方法通常是通过逐个插入序列中的关键字来完成的。以下是一种常见的方法：创建一个空的二叉查找树。从序列中取出第一个关键字作为根结点，将其插入到二叉查找树中。对于序列中的每个后续关键字，按照以下规则进行插入：从根结点开始，递归地比较要插入关键字和当前结点关键字。如果要插入关键字小于当前结点的关键字，则向其左子树移动；如果该大于当前结点的关键字，则向其右子树移动。重复步骤③直到遇到一个空的子结点（即空指针），表示找到了插入位置，将要插入关键字作为新结点插入到这个空的子结点位置。重复步骤③和④，直到遍历完整个序列，插入所有关键字为止。已知关键字序列为37、21、30、50、35、40、12，其二叉查找树的构造过程如下图4）二叉查找树上结点的平均查找长度二叉查找树和折半查找判定树类似，各结点的成功查找长度就是结点所在层数。因此，二叉查找树的平均查找长度不仅与结点个数n有关，而且与树形有关。同一组数，插入顺序不同，构造的树形不同，其查找成功的平均查找长度也不一定相同。例如，由2、4、6、8、10和6、10、2、8、4所构造的二叉查找树如图a)、b)所示。b)查找成功的平均查找长度？？？

03排序的概念内部排序：是指待排序数据元素存放在计算机随机存储器中进行的排序过程。外部排序：指待排序数据元素的数量较大，内存一次不能容纳全部数据元素，在排序过程中尚需对外存进行访问的排序过程

衡量一个排序算法，通常使用以下三个性能指标：1）时间复杂度。时间复杂度主要取决于关键字的比较次数和数据元素的移动次数。2）空间复杂度。排序算法所需要的辅助空间取决于所用的算法本身。3）稳定性。

排序算法的稳定性是指在待排序的一组数据中，若有两个相同的关键字在排序前和排序后，它们的先后顺序没有发生变化，则称这种排序算法是稳定的，否则是不稳定的。04常用的内部排序根据排序方法进行一趟的基本操作不同，内部排序方法分为下面几大类：基于“插入”思想的排序方法执行一趟是将一个元素“插入”到有序序列中仍然有序，使有序部分扩大。这类方法有：直接插入排序折半插入排序2路插入排序SHELL排序基于“交换”思想的排序方法执行一趟是通过交换“逆序”元素使之到有序序列中，使有序部分扩大。这类方法有：冒泡（标准交换）排序奇偶（成对）交换排序穿梭排序快速排序基于“选择”思想的排序方法执行一趟是通过出当前无序部分的最小元素放到有序序列的后面，使有序部分扩大。这类方法有：简单选择排序锦标赛（打擂台）排序堆排序其他思想的排序方法基数排序计数排序基于“归并”思想的排序方法执行一趟是通过归并两个短的有序序列为一个有序序列，使有序部分扩大。这类方法有：2路归并排序多路归并排序1.直接插入排序其基本思想是将待排序线性表分为有序序列和无序序列两部分，将无序序列的一个或几个数据元素插入到有序序列的合适位置，直到全部数据元素有序为止。

2.冒泡排序

基本思想是对所有相邻元素的关键字进行比较，如果是逆序，则将其交换，最终达到有序。冒泡排序方法简单，应用广泛。例10-6将9，5，2和4这4个数据元素用冒泡排序的方法进行排序。先把4个数依次存入x[1..4]数组中，具体排序过程如图所示。

3.直接选择排序直接选择排序的基本思想是将未排好序的序列中最小元素依次添加到已排好序的序列的一端。将5、8、2、4、6、1用直接选择排序方法排序，方法如图所示，圆圈内数字为已排好序的数。

05排序方法应用举例例10-8

青年歌手大赛，有10位评委进行打分，每位选手的最后得分为：去掉1个最高分和1个最低分后，8位评委的总分。要求编写一个通用程序，输入各选手的编号、各位评委的评分，输出各选手的编号、总分及名次。采用模块化思想，可设置4个函数如下：①sum1函数。计算各选手总分。②sort1函数。应用冒泡排序方法，总分由高到低排序。③print1函数。输出各选手的编号、总分和名次。④main主函数。输入各选手的编号、各位评委的评分，分别调用以上3个函数。定义标识符说明：M：符号常量，设有10位评委。N：符号常量，设有5位选手。a[1..M]：10位评委的打分。b[1..N]：5位选手最后得分。c[1..N]：选手的编号。intsum1(intx[],intn) /*计算各位选手总分*/{inti,max,min,s; /*max和min分别记录最高分和最低分，s记录评分和*/max=min=s=x[1]; /*设置初值*/for(i=2;i<=n;i++){if(x[i]>max)max=x[i]; /*求最高分*/if(x[i]<min)min=x[i]; /*求最低分*/s=s+x[i]; /*评委总分*/}s=s-max-min; /*去掉1个最高分和1个最低分后选手的最后得分*/returns;}v