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 内部排序方法 • 插入排序 - 将一个待排序序列的元素，逐个按其关键字的大小 插入到前面已排好的有序序列的适当位置上，直到 待排序元素全部插入完为止。 • 选择排序 - 每次从待排序序列中选择一个关键字最小的元素， （当需要按关键字升序排列时），顺序排在已排序 序列的最后，直至全部排完。 • 交换排序 - 两两比较待排序序列中的元素，并交换不满足顺序 要求的各对记录，直到全部满足顺序要求为止