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