第九章排序(Sort) 2007.9
第九章 排序 (Sort) 2007.9
主要内容 91排序的基本概念 92插入排序 93交换排序 94选择排序 95各种排序方法的比较 排序( Sorting)是数据处理中一种很重要的运算 同时也是很常用的运算,一般数据处理工作25%的 时间都在进行排序
主要内容 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 各种排序方法的比较 排序（Sorting）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25%的 时间都在进行排序
91排序的基本概念
9.1 排序的基本概念
排序的对象:表 由一组记录组成的文件 排序的依据:关键字(key) 关键字(key),记录中的一个属性,是任何一种可比的有 序数据类型 排序的顺序: 升序/降序 排序定义: 将一组记录按某关键字递增或递减排列的过程。 内部排序与外部排序 文件是否整个存放于内存,排序时是否需要涉及内、外 存的数据交换
排序的对象：表 由一组记录组成的文件。 排序的依据：关键字（key） 关键字（key）,记录中的一个属性, 是任何一种可比的有 序数据类型 排序的顺序： 升序/降序 排序定义： 将一组记录按某关键字递增或递减排列的过程。 内部排序与外部排序： 文件是否整个存放于内存，排序时是否需要涉及内、外 存的数据交换
算法的性能评价 时间复杂度 比较次数、移动次数、数据规模、数据的初 始状态 空间复杂度 辅助空间 稳定性 对于具有同一排序关键字的多个记录,若排序后,记 录的相对次序不变,则称此排序方法是稳定的,否则 称为不稳定的。 算法的复杂度
算法的性能评价 时间复杂度： 比较次数、移动次数、数据规模、数据的初 始状态 空间复杂度： 辅助空间 稳定性 对于具有同一排序关键字的多个记录，若排序后，记 录的相对次序不变，则称此排序方法是稳定的，否则 称为不稳定的。 算法的复杂度