软件开发技术基础 第4版 课件 2.查找和排序

查找和排序查找基本概念

查找表:

由同一类数据构成的用于查找的集合称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。

2查找基本概念静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。

3查找基本概念平均查找长度：

为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：4其中：在等概率条件下（

Pi=1/n）这时平均查找长度为：1．顺序查找顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。5顺序表查找的平均查找长度为：2．折半查找(也称二分查找)6假定元素按关键字的值升序排列，折半查找的思路是将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。

2．折半查找(也称二分查找)7折半查找算法的步骤描述如下：①设置查找区间初值，设下界low=0，设上界high=length-1②若low≤high则计算中间位置mid=(low+high)/2③若key<data[mid]，则设high=mid-1并继续执行步骤②；若key>data[mid]，则设low=mid+1并继续执行步骤②；若key=data[mid]则查找成功，返回目标元素位置mid+1

（位置从1计数）。④若当low=high时，key!=data[mid]则查找失败，返回0。

2．折半查找(也称二分查找)西安交通大学计算机教学实验中心8对给定有序数列{5，6，11，17，21，23，28，30，32，40}进行半查找算法，查找关键字值为30的数据元素。则查找过程如下：第1次：{5，6，11，17，21，23，28，30，32，40}

low=0mid=(0+9)/2=4high=9第2次：{5，6，11，17，21，23，28，30，32，40}

low=5mid=7high=9排序基本概念

排序的定义为：假设含n个记录的序列为{R1，R2，…，Rn}，其相应的关键字序列为{K1,K2,…，Kn}。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1≤Kp2≤…≤Kpn，按此固有关系将最初的记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。西安交通大学计算机教学实验中心9排序基本概念

排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法

10排序基本概念

内部排序方法有很多类型。按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复杂度大约为O(nlog2n)。西安交通大学计算机教学实验中心111、直接插入排序

西安交通大学计算机教学实验中心12初始状态：[35] 22 16 19 22第1趟：[22 35] 16 19 22第2趟：[16 22 35] 19 22第3趟：[16 19 22 35] 22第4趟：[16 19 22 22 35]直接插入排序执行过程在序列{35，22，16，19，22}上应用插入排序的过程，为了对序列中相同记录加以区别，使用了下划线。

2、简单选择排序西安交通大学计算机教学实验中心13在序列{35，22，16，19，22}上应用简单选择排序的过程。

初始状态：[35 22 16 19 22]

第1趟：[16] [22 35 19 22]

第2趟：[16 19] [35 22 22]

第3趟：[16 19 22]

[35 22]

第4趟：[16 19 22 22] [35]3、冒泡排序西安交通大学计算机教学实验中心14基本思路：第一趟排序对全部记录R1，R2，…，Rn自左向右顺次两两比较，若Rk大于Rk+1则交换Rk和Rk+1(k=1,2,…,n-1)，第一趟排序完成后Rn成为序列中最大记录。第二趟排序对序列前n-1个记录采用同样的比较和交换方法，第二趟排序完成后Rn-1成为序列中仅比Rn小的次大的记录。第三趟排序对序列前n-2个记录采用同样处理方法。如此做下去，最多做n-1趟排序，整个序列就排序完成。3、冒泡排序西安交通大学计算机教学实验中心15

下图显示了在序列{35，22，16，19，22}上应用冒泡排序的过程。

初始状态：3522 16 19 [22

第1趟：2216 19 22 [35]

第2趟：1619 22 [22

[35]

第3趟：1619 [22

22 [35]

第4趟：16[19

22 22 [35]4、快速排序西安交通大学计算机教学实验中心16任取待排序序列中某个记录S(例如第一个记录)作为基准，经过比较和交换，将整个序列划分为如下形式：{左侧子序列}S{右侧子序列}并且满足：

①左侧子序列中所有记录的关键字都小于或等于S的关键字。②右侧子序列中所有记录的关键字都大于或等于S的关键字。然后分别对左右两个子序列重复执行上述过程，直到排序完成4、快速排序西安交通大学计算机教学实验中心17

在{22,35,27,16,45,19,22}上应用划分算法（即一趟快速排序）4、快速排序西安交通大学计算机教学实验中心18

当22的位置已经确定后，只需对{19，16}和{27,45,35,22}分别排序即可。可分别取19和27为基准元素。

{22，35，27，16，45，19，22}

{19，16}22{27，45，35，22}