第九章排序 n概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序 小结
概述 排序:将一组杂乱无章的数据按一定的规律 顺次排列起来。 数据表( datalist):它是待排序数据对象的有限 集合。 关键码(ken):通常数据对象有多个属性域,即 多个数据成员组成,其中有一个属性域可用 来区分对象,作为排序依据。该域即为关键 码。每个数据表用哪个属性域作为关键码, 要视具体的应用需要而定。即使是同一个表, 在解决不同问题的场合也可能取不同的域做 关键码
n主关键码:如果在数据表中各个对象的关键码 互不相同,这种关键码即主关键码。按照主关 键码进行排序,排序的结果是唯一的。 n次关键码:数据表中有些对象的关键码可能相 同,这种关键码称为次关键码。按照次关键码 进行排序,排序的结果可能不唯 排序算法的稳定性:如果在对象序列中有两个 对象m和,它们的关键码kn=k,且在排 序之前,对象n排在r前面。如果在排序之后, 对象nn仍在对象m的前面,则称这个排序方法 是稳定的,否则称这个排序方法是不稳定的
n内排序与外排序:内排序是指在排序期间数据 对象全部存放在内存的排序;外排序是指在排 序期间全部对象个数太多,不能同时存放在内 存,必须根据排序过程的要求,不断在内、外 存之间移动的排序。 排序的时间开销:排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算 般都按平均情况进行估算。对于那些受对象关 键码序列初始排列及对象个数影响较大的,需 要按最好情况和最坏情况进行估算
静杰推序:排序的过程是对数据对象本身进 行物理地重排,经过比较和判断,将对象移 到合适的位置。这时,数据对象一般都存放 在一个顺序的表中。 n动态排序:给每个对象增加一个链接指针, 在排序的过程中不移动对象或传送数据,仅 通过修改链接指针来改变对象之间的逻辑顺 序,从而达到排序的目的。 ■算法执行时所需的附加存储:评价算法好坏 的另一标准。 静态排序过程中所用到的数据表类定义,体 现了抽象数据类型的思想