C语言程序设计 清华大学 郑莉 安颖莲
Page 1
第七讲 查找与排序算法参考书：,计算机程序设计基础,第十章
,数据结构（ C语言版）,第九章
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
排序算法
- 直接插入排序
- 简单选择排序
- 起泡法排序
查找算法
- 顺序查找
- 折半查找
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
排序排序 是计算机程序设计中的一种重要操作，
它的功能是将一个 数据元素 的任意序列，重新排列成一个按 关键字 有序的序列。
- 数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
- 关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
内部排序与外部排序
内部排序,待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序,待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
C语言程序设计 清华大学 郑莉 安颖莲
Page 5
内部排序方法
插入排序
- 将一个待排序序列的元素，逐个按其关键字的大小插入到前面已排好的有序序列的适当位置上，直到待排序元素全部插入完为止。
选择排序
- 每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
交换排序
- 两两比较待排序序列中的元素，并交换不满足顺序要求的各对记录，直到全部满足顺序要求为止。
C语言程序设计 清华大学 郑莉 安颖莲
Page 6
直接插入排序在插入类排序方法中，因寻找插入位置的方法不同，又分为不同的插入排序方法，其中最简单的是：直接插入排序。下面举例说明：
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
C语言程序设计 清华大学 郑莉 安颖莲
Page 7
简单选择排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是：简单选择排序。下面举例说明：
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
起泡排序最简单的交换排序方法 —— 起泡排序对具有 n个元素的序列按升序进行起泡排序的步骤：
首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第 n-1和第 n个元素进行了比较和交换。此过程称为第一趟起泡排序。
经过第一趟，最大的元素便被交换到第 n个位置。
对前 n-1个元素进行第二趟起泡排序，将其中最大元素交换到第 n-1个位置。
如此继续，直到某一趟排序未发生任何交换时，
排序完毕。对 n个元素的序列，起泡排序最多需要进行 n-1趟。
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
起泡排序举例对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
查找
查找
- 所谓查找，就是在一个数据元素的集合中，按照某种方式找出所需要的特定数据元素的过程。
两种最简单的查找方法：
- 顺序查找从数据序列第一个元素开始，将给定值逐个与各元素的关键值比较，直到找到相等者。若找不到相等者，便是查找不成功。
- 折半查找（二分法查找）
对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，
直至找到或找不到为止。
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
折半查找举例用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
查找与排序算法综合应用举例
题目：使用前面介绍的三种排序、两种查找算法，对若干人的姓名（字符串）进行排序和查找。
编程要点：
- 查找、排序算法如前所述
- 对若干字符串进行排序，为避免大量的数据交换，
应使用指针数组，存放每个字符串的首地址，当排序过程中需要交换两字符串时，只交换对应的指针数组元素即可。
- 字符串比较可以使用函数 strcmp()
程序,7-1.c
Page 1
第七讲 查找与排序算法参考书：,计算机程序设计基础,第十章
,数据结构（ C语言版）,第九章
C语言程序设计 清华大学 郑莉 安颖莲
Page 2
本讲主要内容
排序算法
- 直接插入排序
- 简单选择排序
- 起泡法排序
查找算法
- 顺序查找
- 折半查找
C语言程序设计 清华大学 郑莉 安颖莲
Page 3
排序排序 是计算机程序设计中的一种重要操作，
它的功能是将一个 数据元素 的任意序列，重新排列成一个按 关键字 有序的序列。
- 数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
- 关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
C语言程序设计 清华大学 郑莉 安颖莲
Page 4
内部排序与外部排序
内部排序,待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序,待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
C语言程序设计 清华大学 郑莉 安颖莲
Page 5
内部排序方法
插入排序
- 将一个待排序序列的元素，逐个按其关键字的大小插入到前面已排好的有序序列的适当位置上，直到待排序元素全部插入完为止。
选择排序
- 每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
交换排序
- 两两比较待排序序列中的元素，并交换不满足顺序要求的各对记录，直到全部满足顺序要求为止。
C语言程序设计 清华大学 郑莉 安颖莲
Page 6
直接插入排序在插入类排序方法中，因寻找插入位置的方法不同，又分为不同的插入排序方法，其中最简单的是：直接插入排序。下面举例说明：
初始状态,[5] 4 10 20 12 3
插入操作,1 [4] [4 5] 10 20 12 3
2 [10] [4 5 10] 20 12 3
3 [20] [4 5 10 20] 12 3
4 [12] [4 5 10 12 20] 3
5 [3] [3 4 5 10 12 20]
C语言程序设计 清华大学 郑莉 安颖莲
Page 7
简单选择排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是：简单选择排序。下面举例说明：
[5 4 10 20 12 3]初始状态：
3 [4 10 20 12 5]
3 4 [10 20 12 5]
第 i 次选择后，将选出的那个记录与第 i 个记录做 交换 。
3 4 5 [20 12 10]
...,..
C语言程序设计 清华大学 郑莉 安颖莲
Page 8
起泡排序最简单的交换排序方法 —— 起泡排序对具有 n个元素的序列按升序进行起泡排序的步骤：
首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第 n-1和第 n个元素进行了比较和交换。此过程称为第一趟起泡排序。
经过第一趟，最大的元素便被交换到第 n个位置。
对前 n-1个元素进行第二趟起泡排序，将其中最大元素交换到第 n-1个位置。
如此继续，直到某一趟排序未发生任何交换时，
排序完毕。对 n个元素的序列，起泡排序最多需要进行 n-1趟。
C语言程序设计 清华大学 郑莉 安颖莲
Page 9
起泡排序举例对整数序列 8 5 2 4 3 按升序排序
8
5
2
4
3
5
2
4
3
8
2
4
3
5
8
2
3
4
5
8
2
3
4
5
8
初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的
C语言程序设计 清华大学 郑莉 安颖莲
Page 10
查找
查找
- 所谓查找，就是在一个数据元素的集合中，按照某种方式找出所需要的特定数据元素的过程。
两种最简单的查找方法：
- 顺序查找从数据序列第一个元素开始，将给定值逐个与各元素的关键值比较，直到找到相等者。若找不到相等者，便是查找不成功。
- 折半查找（二分法查找）
对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，
直至找到或找不到为止。
C语言程序设计 清华大学 郑莉 安颖莲
Page 11
折半查找举例用折半查找法，在下列序列中查找值为 21的元素：
L=1
5 13 19 21 37 56 64 75 80 88 92
H=11M =INT((L+H)/2)=6
5 13 19 21 37
L=1 H=M-1=5 M=INT((L+H)/2)=3M
21 37
H
L=M+1=4
L
M=INT((L+H)/2)=4
M
C语言程序设计 清华大学 郑莉 安颖莲
Page 12
查找与排序算法综合应用举例
题目：使用前面介绍的三种排序、两种查找算法，对若干人的姓名（字符串）进行排序和查找。
编程要点：
- 查找、排序算法如前所述
- 对若干字符串进行排序，为避免大量的数据交换，
应使用指针数组，存放每个字符串的首地址，当排序过程中需要交换两字符串时，只交换对应的指针数组元素即可。
- 字符串比较可以使用函数 strcmp()
程序,7-1.c
