数据结构与算法（C语言） 教案 第06章 查找与排序

千等教育

数据结构与算法（C语言篇）

教学设计

课程名称：数据结构与算法rc语言篇）

授课年级：____________________________________

授课学期：____________________________________

教卵发名：____________________________________

2020年03月01日

计划

课程名称第6章查找与排序4学时

学时

内容分析本章主要介绍查找、排序

教学目标

要求学生掌握常用的查找算法、掌握常用的排序算法、掌握查找算法的

与

代码编写方法、掌握排序算法的代码编写方法

教学要求

教学重点查找、排序

教学难点查找、排序

教学方式课堂讲解及ppt演示

第一课时

(查找、排序)

Q内容回顾

1.回顾上节内容，引出本课时主题。

上节已经介绍了章图，本章将主要介绍算法中的常用操作一一查找与排

序。查找与排序作为数据处理的基本操作，是学习编程必须掌握的。查找是

在给定的数据集合(表)中搜索指定的数据元素。排序是将数据集合中的各

个数据元素按照指定的顺序进行排列。查找与排序的算法很多，根据数据集

合的不同特点使用不同的查找与排序算法，可以节省空间与时间，提高程序

效率。本章将重点围绕查找与排序算法的原理与代码实现进行介绍。

2.明确学习目标

教(1)能够掌握顺序查找

(2)能够掌握折半查找

学(3)能够掌握分块查找

(4)能够掌握哈希查找

过(5)能够掌握排序的概念

(6)能够掌握直接插入排序

程(7)能够掌握希尔排序

Q知识讲解

＞顺序查找

顺序查找(SequentialSearch)又可以称为线性查找，是最基本的查

找技术。顺序查找的基本原理是从数据集合中的第一个(或最后一个)数据

元素开始，逐个与给定值进行对比。如果某个数据元素与给定值相同，则查

找成功。如果查找到最后一个(或第一个)数据元素，都与给定值不同，则

查找失败。

顺序查找算法比较简单，以整型数据为例，代码参考教材6.1.1节。

＞折半查找

当数据集合中的数据元素无序排列时，只能采用顺序查找，而如果这个

数据集合中的数据元素是有序的，则可以采用折半查找来提高查找效率。

折半查找(BinarySearch)又称为二分查找•折半查找的基本原理是

在有序的表中取中间的数据作为比较对象。如果查找的值与中间的值相等，

则查找成功；如果查找的值小于中间的值，则到有序表的左半区继续查找；

如果查找的值大于中间的值，则到有序表的右半区继续查找。不断重复上述

步骤，直到查找成功，如图所示。

14

"'给定值

lowvhigh

第一次折半

0123456789101112

131920

low«high

第二次折半

▼▼

0123456789101112

11：121314，5，6，7181920212223

查找成功

>分块查找

分块查找(BlockSearch)又称为索引顺序查找，是介于顺序查找与折

半查找之间的查找算法，也是顺序查找算法的一种改进算法。

分块查找类似于从书籍中查找资料。假设读者需要从一本书中查找资

料，一般的做法是先从目录开始，找到资料所在章节的起始页面，然后从该

起始页向后寻找。这种做法明显要比从书的第一页向后查找快很多。因此，

书籍在编辑时，都会将所有的内容按照一定的规则分成若干块(章)，每一

块再分为若干个小块(节)，并设置它们的位置(页)，形成一个目录，通

过这个目录即可实现快速查找。这个目录就是索引表，这种查找方式就是分

块查找。

分块查找需要将数据集合分成若干个块，并且这些块满足两个条件。

(1)块内无序，即每一块中的数据不要求有序。

(2)块间有序，即块与块之间是有序的。后一个块中的各个数据元素都

比前一个块中的任何数据元素大。例如，第一个块中的数据元素都小于30,

那么第二个块中的数据元素都必须大于等于30。

>哈希查找

1.哈希函数的构造方法

哈希查找(HashSearch)算法是通过计算数据元素的存储地址来进行

查找的一种算法。算法的原理是查找时通过给定值k以及对应关系f,便

可以找到k值所对应的哈希地址f(k)(不需要比较直接获得查找目标)。

这种对应关系f就是哈希函数，通过这个思想建立的表称为哈希表。

哈希函数的构造方法有很多，具体如下。

(1)直接定址法。取关键字或关键字的某个线性函数值作为哈希地址,

即H(key)=key或H(key)=aXkey+b(a,b为常数)。

(2)数字分析法。取关键字中某些取值较均匀的数字位作为哈希地址。

当关键字的位数很多时，可以通过对关键字的各位进行分析，去掉分布不均

匀的位。这种方法只适合于所有关键字已知的情况。通过分析分布情况将关

键字取值区间转化为一个较小的关键字取值区间。

(3)平方取中法。取关键字平方后的中间几位作为哈希地址。

(4)折叠法。将关键字分割成位数相同的几个部分(最后一部分的位数

可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。这种方

法适用于关键字位数比较多，且关键字中每一位上数字分布大致均匀的情

况。

(5)除留余数法。取关键字被某个不大于哈希表表长m的数p除后

所得的余数作为哈希地址(P为素数)。

(6)随机数法。选择一个随机函数，取关键字的随机函数值作为其哈希

地址，即H(key)=random(key),其中random。为随机函数。该方法适用于

关键字长度不等的情况。

2.哈希冲突

由于通过哈希函数产生的哈希地址是有限的，而在数据比较多的情况

下，经过哈希函数处理后，不同的数据可能会产生相同的哈希地址，这就造

成了哈希冲突，如图所示。

关键字

>排序的概念

排序指的是将无序的记录按照其中某个(或某些)关键字的大小以递增

或递减的顺序排列起来的操作。其确切的定义为：假设有n个数据元素的

序列(R1,R2，…Rn),其相应关键字的序列是(K1,K2,-Kn),要

求通过排序找出下标1,2,-n的一种排列P1,P2,…Pn,使得相应关

键字满足非递减(或非递增)关系KplWKp2W…<Kpn,从而得到一

个按关键字有序排列的记录序列(Rpl,Rp2…Rpn)»

按照排序过程中涉及的存储器的不同，可以将排序分为内部排序与外部

排序。内部排序指的是待排序的记录数较少，所有的记录都能存放在内存中

进行排序。外部排序指的是待排序的记录数太多，不可能把所有的记录存放

在内存中，排序过程中必须在内存与外存之间进行数据交换。

＞直接插入排序

1.直接插入排序概述

直接插入排序(InsertionSort)是一种简单直观的排序算法，其工作

原理是先构建有序序列，然后在已排序序列中从后向前扫描，为未排序的数

据找到相应位置并将其插入。

直接插入排序算法的具体操作步骤如下所示。

(1)从序列的第一个元素开始，该元素被认定为已排序。

(2)在已排序的元素序列中从后向前扫描，为下一个元素寻找位置。

(3)如果已排序的元素大于新插入的元素，则将已排序元素移动到下

一位。

(4)重复步骤(3),直到已排序元素小于或等于新插入的元素。

(5)插入新元素。

(6)重复步骤(2)〜(5)。

2.直接插入排序代码实现

直接插入排序的代码参考教材6.2.2节。

＞希尔排序

1.希尔排序概述

希尔排序(ShellSort)是希尔(DonaldShell)于1959年提出的

一种排序算法。希尔排序同样是一种插入排序，它是直接插入排序经过改进

之后的一个更高效的版本，也称为缩小增量排序。希尔排序与直接插入排序

的不同之处在于，希尔排序会优先比较距离较远的元素。

希尔排序的核心操作是将序列按照增量(增量等于组的数量)进行分组,

然后对每一组中的序列使用直接插入排序算法进行排序。当所有组中的序列

都完成排序后，增量变小，按照减小的增量再次分组(分组不影响元素的位

置)，分组后再进行直接插入排序，以此类推(增量越小，每组的元素就越

多)。当增量减小为1时，整个序列分为一组，算法结束。

希尔排序在选择增量时，可以使增量gap=length/2(length为序列长

度)，缩小增量可以使用gap=gap/2的方式，这种增量可以用一个序列来表

示，称为增量序列。

2.希尔排序代码实现

希尔排序算法的代码参考教材6.2.3节。

第二课时

(排序)

Q内容回顾

i.回顾上节内容，引出本课时主题。

上节已经介绍了顺序查找、折半查找、分块查找、哈希查找、排序的概

念、直接插入排序和希尔排序，下面将介绍直接选择排序、堆排序、冒泡排

序、快速排序和归并排序。

2.明确学习目标

(1)能够掌握直接选择排序

(2)能够掌握堆排序

(3)能够掌握冒泡排序

(4)能够掌握快速排序

(5)能够掌握归并排序

Q知识讲解

＞直接选择排序

i.直接选择排序概述

直接选择排序(SelectionSort)是比较稳定的排序算法，其时间复杂度

在任何情况下都是0(n2)。

直接选择排序是一种简单直观的排序算法，排序过程中，无须占用额外

的空间。直接选择排序的工作原理是：首先在未排序的序列中找到最小(大)

元素，存放到已排序序列的末尾；然后从剩余未排序元素中寻找最小(大)

元素，放到已排序序列的末尾；以此类推，直到所有元素排序完毕。

由上述描述可知，直接选择排序就是反复从未排序的序列中取出最小

(大)的元素，加入另一个序列，最后得到已经排好的序列。接下来通过具

体的序列对直接选择排序算法进行说明。如图所示，创建一个原始的未排序

的序列。

未排序@(7)(4)000

2.直接选择排序代码实现

直接选择排序的代码参考教材6.2.4节。

＞堆排序

1.堆排序概述

堆排序(HeapSort)是利用数据结构堆设计的一种排序算法。堆是一个

近似完全二叉树的结构。如果堆中每个结点的值都大于或等于其左右孩子的

值，则该堆称为大顶堆：如果堆中每个结点的值都小于或等于其左右孩子的

值，则该堆称为小顶堆，如图所示。

2

?'t°2F

3(18)(15)43(12).4

大顶堆小顶堆

2.堆排序代码实现

堆排序的代码参考教材6.2.5节。

>冒泡排序

1.冒泡排序概述

冒泡排序(BubbleSort)是一种简单且经典的排序算法。冒泡排序的核

心思想是重复遍历整个序列，从第一个元素开始，两两比较相邻元素的大小,

如果反序则交换，直到整个序列变为有序为止。

冒泡排序算法的具体操作步骤如下所示。

(1)比较相邻元素，从第一个元素开始，即第一个元素与第二个元素比

较，如果前一个元素大于后一个元素就进行交换。

(2)每次比较完成后，移动到下一个元素继续进行比较，直到比较完最

后一个元素与倒数第二个元素。

(3)所有元素比较完成后(一轮比较)，序列中最大的元素在序列的末

尾。

(4)重复上述3个步骤。

2.冒泡排序代码实现

冒泡排序的代码参考教材6.2.6节。

>快速排序

快速排序(QuickSort)的核心思想是通过一轮排序将未排序的序列分为

独立的两部分，使得一部分序列的值比另一部分序列的值小，然后分别对这

两部分序列继续进行排序，以达到整个序列有序。

快速排序使用分治法将一个序列分为两个子序列，其具体的算法描述如

下。

(1)从序列中选出一个元素，作为基准值。

(2)重新排序，将所有比基准值小的元素放到基准值前，所有比基准值

大的元素放到基准值后(与基准值相同的元素可以到任一边)。

(3)采用递归的思想对小于基准值的子序列和大于基准值的子序列排

序。

在上述算法描述的基础上，快速排序可以设计出很多版本。接下来将通

过具体的序列展示快速排序的两个版本，分别为单指针遍历法与双指针遍历

法(指针指的是方向选择，不是语法意义上的指针)。

1.单指针遍历法

如图所示，创建一个无序的数字序列。

未排序序列

57164832

2.单指针遍历法实现快速排序

采用单指针遍历法实现快速排序代码参考教材6.2.7节。

3.双指针遍历法

在单指针遍历法中，每次都是选择一个元素与基准值进行比较，而双指

针遍历法是同时选择两个元素与基准值进行比较。如图所示，创建一个无序

序列。

未排序序列

1517101614181312

ij

4.双指针遍历法实现快速排序

采用双指针遍历法实现快速排序，示例代码参考教材6.2.7节。

>归并排序

1.归并排序概述

归并排序(MergingSort)是利用归并的思想设计的一种排序算法，该算

法是采用分治法的一个非常典型的应用。归并排序是一种稳定