1、 第8章 排 序 8.1 排序技术概述 8.2 插入排序8.3 选择排序8.4 交换排序8.5 归并排序8.6 基数排序8.7 外部排序概述 8.8 本章小结8.1 排序技术概述从操作角度看，排序是线性结构的一种操作。为了提高排序效率，人们已对排序进行了许多研究，提出了许多方法。排序就是按照某种规则，为一组给定的对象排列次序。 排序的主要目的是：在排好序的集合中能够快速查找（检索）一个元素。所谓“内部”排序，就是指整个排序过程都是在内存中进行的。如果排序的数据项很多，内存不足以存放得下全部数据项时，排序过程就需要对外存进行存取访问，也就是“外部”排序。本章的内容以内部排序为主，对外部排序只进行
2、简单地介绍。 我们把查找时关注或使用的数据叫做关键 （key）， 以是数据 中的一个 性，也 以是 个 性的组合。关键 以 所在的 项数据 。在 项数据 中，关键所取的 叫做键 。在本章中，为了 出排序法本 的内容，我们简 项数据的 性个数。排序的数据都只 一个 性， 个 性就是关键 ， 关键 的 是整 。我们 以把排序看 是一种定在某种数据集合 的操作。本章所 的 种内部排序，都以 为是在一 数组 种线性数据结构 定 的操作。 能是一组一排列的数据元素排列一个按键 序的序列。对排序为currency1的定 D1,D2,“,DN为 N项数据的序列， 中Di（1iN） 序列中fii项数据，N项数据对fl的键 序列为K1,K2,“,KN。排序操作是 数据排列 一个按键 序的序列Rp1,Rp2,“,RpN，使得fl的键 足p1p2“pN（ 时序列 “序”）或p1p2“pN（ 时序列 “序”）。注意：在 定 ”述中所用的或 个 ，是用 的关 。对数 ， 是 关的或对 ， 是指在 中所排列 的或。对不 的数据，我们 以规定不的 规则 或的 。如果在数据序列中， 多个 键 的数据，在排序，数据 的对次序 不 ， 的排序方法 作是 定的， 则 为是不 定的。
