第8章排序 8I排序技术概述 8,2入排序 8,3选择排序 8,4交换排序 85归并排序 86基数排序 87外部排序概述 8.8本章小堵结
第8章 排 序 8.1 排序技术概述 8.2 插入排序 8.3 选择排序 8.4 交换排序 8.5 归并排序 8.6 基数排序 8.7 外部排序概述 8.8 本章小结
8.1排序技术概述 从操作角度看,排序是线性 结构的一种操作。 为了提高排序效率,人们已 对排序进行了许多研究,提出了 许多方法
8.1 排序技术概述 从操作角度看，排序是线性 结构的一种操作。 为了提高排序效率，人们已 对排序进行了许多研究，提出了 许多方法
排序就是按照某种规则 为一组给定的对象排列次序 排序的主要目的是:在排好 序的集合中能够快速査找(检索) 元素
排序就是按照某种规则， 为一组给定的对象排列次序。 排序的主要目的是：在排好 序的集合中能够快速查找（检索） 一个元素
所谓“内部”排序,就是指整个排 序过程都是在内存中进行的。 如果排序的数据项很多,内存不足 以存放得下全部数据项时,排序过程就 需要对外存进行存取访问,也就是“外 部”排序。 本章的内容以内部排序为主,对外 部排序只进行简单地介绍
所谓“内部”排序，就是指整个排 序过程都是在内存中进行的。 如果排序的数据项很多，内存不足 以存放得下全部数据项时，排序过程就 需要对外存进行存取访问，也就是“外 部”排序。 本章的内容以内部排序为主，对外 部排序只进行简单地介绍
我们把查找时关注或使用的数据 叫做关键字(key),它可以是数据 信息当中的一个属性,也可以是几个 属性的组合。 关键字可以代表其所在的那项数 据信息、。在这项数据信息当中,关键 字所取的值叫做键值
我们把查找时关注或使用的数据 叫做关键字（key），它可以是数据 信息当中的一个属性，也可以是几个 属性的组合。 关键字可以代表其所在的那项数 据信息。在这项数据信息当中，关键 字所取的值叫做键值
在本章中,为了突出排序 算法本身的内容,我们简化各项 数据的属性个数 假设待排序的数据都只有 个属性,这个属性就是关键字, 并且关键字的类型是整型
在本章中，为了突出排序 算法本身的内容，我们简化各项 数据的属性个数。 假设待排序的数据都只有 一个属性，这个属性就是关键字， 并且关键字的类型是整型
我们可以把排序看成是一种定 义在某种数据集合上的操作 本章所讲的各种内部排序,都 可以认为是在一维数组这种线性数 据结构上定义的操作。其功能是将 组任一排列的数据元素重新排列 成一个按键值有序的序列
我们可以把排序看成是一种定 义在某种数据集合上的操作。 本章所讲的各种内部排序，都 可以认为是在一维数组这种线性数 据结构上定义的操作。其功能是将 一组任一排列的数据元素重新排列 成一个按键值有序的序列
对排序更为确切的定义: 假设{D1,D2r…,D1}为含有N项数据 的序列,其中D:(1≤i≤N)表示序列中 第i项数据,N项数据对应的键值序列为 IK,K KI 排序操作是将这些数据重新排列成 个按键值有序的新序列 ARR R 使得相应的键值满 足条件p1≤ pN(此时新序列成 “升序”)或p1≥p2≥…≥pN(此时新 序列成“降序”)
对排序更为确切的定义: 假设{D1,D2, …,DN}为含有N项数据 的序列，其中Di（1≤i≤N）表示序列中 第i项数据，N项数据对应的键值序列为 {K1,K2, …,KN}。 排序操作是将这些数据重新排列成一 个 按 键 值 有 序 的 新 序 列 {Rp1,Rp2, …,RpN}，使得相应的键值满 足条件p1≤p2≤…≤pN（此时新序列成 “升序”）或p1≥p2≥…≥pN（此时新 序列成“降序”）
注意:在上面定义叙述中所用到 的≤或≥这两个比较符号,是通用意义 上的关系比较符。 对于数值型信息,它是表示关系的 小或大;对于字符串来说,它是指在字 典中所排列位置的前或后 对于不同类型的数据,我们可以规 定不同的比较规则来反映≤或≥的含义
注意：在上面定义叙述中所用到 的≤或≥这两个比较符号，是通用意义 上的关系比较符。 对于数值型信息，它是表示关系的 小或大；对于字符串来说，它是指在字 典中所排列位置的前或后。 对于不同类型的数据，我们可以规 定不同的比较规则来反映≤或≥的含义
如果在数据序列中,有多个具 有相同键值的数据,在排序前后, 这些数据之间的相对次序保持不变, 这样的排序方法被称作是稳定的, 否则被称为是不稳定的
如果在数据序列中，有多个具 有相同键值的数据，在排序前后， 这些数据之间的相对次序保持不变， 这样的排序方法被称作是稳定的， 否则被称为是不稳定的