C语言程序设计(清华郑莉安颍莲)chap7

1、C语言程序设计清华大学 郑莉 安颖莲Page 1第七讲第七讲 查找与排序算法查找与排序算法参考书：参考书：计算机程序设计基础计算机程序设计基础第十章第十章 数据结构（数据结构（C C语言版）语言版）第九章第九章C语言程序设计清华大学 郑莉 安颖莲Page 2本讲主要内容本讲主要内容 排序算法排序算法- 直接插入排序直接插入排序- 简单选择排序简单选择排序- 起泡法排序起泡法排序 查找算法查找算法- 顺序查找顺序查找- 折半查找折半查找C语言程序设计清华大学 郑莉 安颖莲Page 3排序排序 排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个它的功能是将

2、一个数据元素数据元素的任意序列，重新排的任意序列，重新排列成一个按列成一个按关键字关键字有序的序列。有序的序列。- 数据元素：数据的基本单位。在计算机中通常作为数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项一个整体进行考虑。一个数据元素可由若干数据项组成。组成。- 关键字：数据元素中某个数据项的值，用它可以标关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。识（识别）一个数据元素。C语言程序设计清华大学 郑莉 安颖莲Page 4内部排序与外部排序内部排序与外部排序 内部排序：内部排序：待排序的数据元素存放在计算机内待排序的数据元素存放

3、在计算机内存中进行的排序过程。存中进行的排序过程。 外部排序：外部排序：待排序的数据元素数量很大，以致待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。中尚需对外存进行访问的排序过程。C语言程序设计清华大学 郑莉 安颖莲Page 5内部排序方法内部排序方法 插入排序插入排序- 将一个待排序序列的元素，逐个按其关键字的大小将一个待排序序列的元素，逐个按其关键字的大小插入到前面已排好的有序序列的适当位置上，直到插入到前面已排好的有序序列的适当位置上，直到待排序元素全部插入完为止。待排序元素全部插入完为止。

4、选择排序选择排序- 每次从待排序序列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。序列的最后，直至全部排完。 交换排序交换排序- 两两比较待排序序列中的元素，并交换不满足顺序两两比较待排序序列中的元素，并交换不满足顺序要求的各对记录，直到全部满足顺序要求为止。要求的各对记录，直到全部满足顺序要求为止。C语言程序设计清华大学 郑莉 安颖莲Page 6直接插入排序直接插入排序在插入类排序方法中，因寻找插入位置的方法不同，又分为不同的插入排序方法，其中最简单的是

5、：直接插入排序。下面举例说明：初始状态：初始状态： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 4 4 4 5 10 20 12 34 5 10 20 12 32 2 1010 4 5 10 20 12 34 5 10 20 12 33 3 2020 4 5 10 20 12 34 5 10 20 12 34 4 1212 4 5 10 12 20 34 5 10 12 20 35 5 33 3 4 5 10 12 203 4 5 10 12 20C语言程序设计清华大学 郑莉 安颖莲Page 7简单选择排序简单选择排序在选择类排序方法中，从待排序序列中选

6、择元素的方法不同，又分为不同的选择排序方法，其中最简单的是：简单选择排序。下面举例说明：5 4 10 20 12 5 4 10 20 12 3 3 初始状态：初始状态：3 3 4 4 10 20 12 5 10 20 12 53 4 10 20 12 3 4 10 20 12 5 5 第 i i 次选择后，将选出的那个记录与第 i i 个记录做交换交换。3 4 5 20 12 3 4 5 20 12 1010 . .C语言程序设计清华大学 郑莉 安颖莲Page 8起泡排序起泡排序最简单的交换排序方法起泡排序对具有n个元素的序列按升序进行起泡排序的步骤：首先将第一个元素与第二个元素进行比较，若为

7、逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。C语言程序设计清华大学 郑莉 安颖莲Page 9起泡排序举例起泡排序举例对整数序列对整数序列 8 5 2 4 3 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐

8、渐上升每趟沉下一个最大的C语言程序设计清华大学 郑莉 安颖莲Page 10查找查找 查找查找- 所谓查找，就是在一个数据元素的集合中，按照某种方式所谓查找，就是在一个数据元素的集合中，按照某种方式找出所需要的特定数据元素的过程。找出所需要的特定数据元素的过程。 两种最简单的查找方法：两种最简单的查找方法：- 顺序查找顺序查找从数据序列第一个元素开始，将给定值逐个与各元素的关从数据序列第一个元素开始，将给定值逐个与各元素的关键值比较，直到找到相等者。若找不到相等者，便是查找键值比较，直到找到相等者。若找不到相等者，便是查找不成功。不成功。- 折半查找（二分法查找）折半查找（二分法查找）对于已按关

9、键字排序的序列，经过一次比较，可将序列分对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。直至找到或找不到为止。C语言程序设计清华大学 郑莉 安颖莲Page 11折半查找举例折半查找举例用折半查找法，在下列序列中查找值为用折半查找法，在下列序列中查找值为2121的元素：的元素：L=1513192137566475808892H=11M =INT(L+H)/2)=6513192137L=1H=M-1=5M=INT(L+H)/2)=3M2137HL=M+1=4LM=INT(L+H)/2)=4MC语言程序设计清华大学 郑莉 安颖莲Page 12查找与排序算法综合应用举例查找与排序算法综合应用举例 题目：使用前面介绍的三种排序、两种查找算题目：使用前面介绍的三种排序、两种查找算法，对若干人的姓名（字符串）进行排序和查法，对若干人的姓名（字符串）进行排序和查找。找。 编程要点：编程要点：- 查找、排序算法如前所述查找、排序算法如前所述- 对若干字符串进行排序，为避免大量的数据交换，对若干字符串进行排序，为避免大量的数据交换，应使用指