第九章排序 概述 插入排序 选择排序 归并排序 口基数非序 外推序
概述 排序:将一组杂乱无章的数据按一定的规律 顺次排列起来。 数据表(aai0它是待排序数据对象的有限 集合。 排序码kep:通常数据对象有多个属性域, 即多个数据成员组成,其中有一个属性域可 用来区分对象,作为排序依据。该域即为排 序码。每个数据表用哪个属性域作为排序码, 要视具体的应用需要而定
」排序算法的稳定性:如果在对象序列中有两 个对象叫和m它们的排序码=k,且 在排序之前,对象排在r前面。如果在排 序之后对象叫仍在对象m的前面,则称这 个排序方法是稳定的,否则称这个排序方法 是不稳定的。 内排序与外排序:内排序是指在排序期间 数据对象全部存放在内存的排序;外排序 是指在排序期间全部对象个数太多,不能 同时存放在内存,必须根据排序过程的要 求,不断在内、外存之间移动的排序
」排序的时间开销:排序的时间开销是衡量 算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动 次数来衡量。 算法运行时间代价的大略估算一般都按平均 情况进行佔算。对于那些受对象排序码序列 初始排列及对象个数影响较大的,需要按最 好情况和最坏情况进行估算。 口算法执行时所需的附加存储:评价算法好 坏的另一标准
待排序数据表的类定义 include <iostream.h> const int DefaultSize =100 template <class Type> class datalist t template <class Type> class element t friend class dataList<Type>; pl rivate. Type key; ∥/排序码 field otherdata:/它数据成员 public Element (: key(0), otherdata(NULL)&
#include <iostream.h> const int DefaultSize = 100; template <class Type> class dataList { template <class Type> class Element { friend class dataList<Type>; private: Type key; //排序码 field otherdata; //其它数据成员 public: Element ( ) : key(0), otherdata(NULL) { }