第九章排序 概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序 小结
概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序 小结
概述 排序:将一组杂乱无章的数据按一定的规律顺 次排列起来。 数据表(dli:它是待排序数据对象的有限 集合。 关健码ke):通常数据对象有多个属性城,即 多个数据成员组成,其中有一个属性域可用来 区分对象,作为排序依据。该域即为关键码。 每个数据表用哪个属性域作为关键码,要视具 体的应用需要而定。即使是同一个表,在解决 不同问题的场合也可能取不同的域做关键码
概述 排序：将一组杂乱无章的数据按一定的规律顺 次排列起来。 数据表(datalist): 它是待排序数据对象的有限 集合。 关键码(key): 通常数据对象有多个属性域，即 多个数据成员组成，其中有一个属性域可用来 区分对象，作为排序依据。该域即为关键码。 每个数据表用哪个属性域作为关键码，要视具 体的应用需要而定。即使是同一个表，在解决 不同问题的场合也可能取不同的域做关键码
主关健码:如果在数据表中各个对象的关键码 互不相同,这种关键码即主关键码。按照主关 键码进行排序,排序的结果是唯一的。 次关键码:数据表中有些对象的关键码可能相 同,这种关键码称为次关键码。按照次关键码 进行排序,排序的结果可能不唯一。 0排序算法的稳定性如果在对象序列中有两个 对象r和,们的关键码k=k,且在排 序之前,对象排在前面。如果在排序之后 对象n仍在对象r的前面,则称这个排序方法 是稳定的,否则称这个排序方法是不稳定的
主关键码: 如果在数据表中各个对象的关键码 互不相同，这种关键码即主关键码。按照主关 键码进行排序，排序的结果是唯一的。 次关键码: 数据表中有些对象的关键码可能相 同，这种关键码称为次关键码。按照次关键码 进行排序，排序的结果可能不唯一。 排序算法的稳定性: 如果在对象序列中有两个 对象r[i]和r[j]，它们的关键码 k[i] == k[j]，且在排 序之前，对象r[i]排在r[j]前面。如果在排序之后， 对象r[i]仍在对象r[j]的前面，则称这个排序方法 是稳定的，否则称这个排序方法是不稳定的
内排序与外排序:内排序是指在排序期间数据 对象全部存放在内存的排序;外排序是指在排 序期间全部对象个数太多,不能同时存放在内 存,必须根据排序过程的要求,不断在内、外 存之间移动的排序。 排序的时间开销:排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算 般都按平均情况进行估算。对于那些受对象关 键码序列初始排列及对象个数影响较大的,需 要按最好情况和最坏情况进行估算
内排序与外排序: 内排序是指在排序期间数据 对象全部存放在内存的排序；外排序是指在排 序期间全部对象个数太多，不能同时存放在内 存，必须根据排序过程的要求，不断在内、外 存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算一 般都按平均情况进行估算。对于那些受对象关 键码序列初始排列及对象个数影响较大的，需 要按最好情况和最坏情况进行估算
静态排序:排序的过程是对数据对象本身进 行物理地重排,经过比较和判断,将对象移 到合适的位置。这时,数据对象一般都存放 在一个顺序的表中。 动态排序:给每个对象增加一个链接指针, 在排序的过程中不移动对象或传送数据,仅 通过修改链接指针来改变对象之间的逻辑顺 序,从而达到排序的目的。 算法执行时所需的附加存储:评价算法好坏 的另一标准。 静态排序过程中所用到的数据表类定义,体 现了抽象数据类型的思想
静态排序: 排序的过程是对数据对象本身进 行物理地重排，经过比较和判断，将对象移 到合适的位置。这时，数据对象一般都存放 在一个顺序的表中。 动态排序: 给每个对象增加一个链接指针， 在排序的过程中不移动对象或传送数据，仅 通过修改链接指针来改变对象之间的逻辑顺 序，从而达到排序的目的。 算法执行时所需的附加存储: 评价算法好坏 的另一标准。 静态排序过程中所用到的数据表类定义，体 现了抽象数据类型的思想
待排序数据表的类定义 #ifndef datalist h #define datalist h #include const int Defaultsize=100 template class datalist t template class Element i private pe key, 关键码 field otherdata 其它数据成员 public: Element(: key(0), otherdata null
待排序数据表的类定义 #ifndef DATALIST_H #define DATALIST_H #include const int DefaultSize = 100; template class datalist { template class Element { private: Type key; //关键码 field otherdata; //其它数据成员 public: Element ( ) : key(0), otherdata(NULL){ }
Type getKey(){ return key;}/提是取关键码 void setKey( const Type x){kegy=x;}∥修改 Element& operator 赋值 Element&x)i this =x;) int operator==( Type &x) //Fthis ==x freturn!( this x);) int operator>=(Type&x)/判]this≥x f return!( this x;)
Type getKey ( ) { return key; }//提取关键码 void setKey ( const Type x ) { key = x; } //修改 Element & operator = //赋值 ( Element & x ) { this = x; } int operator == ( Type & x ) //判this == x { return ! ( this x ); } int operator >= ( Type & x ) //判this x { return ! ( this x; }
template class datalist i public: datalist( int Maxsz= Defaultsize):/构造函数 MaxSize( maxsz ) Currentsize(o i vector=new Element [MaxSz: j void swap( Element&x,/对换 Element &y) f Element temp=x;x=y; y=temp; 3 private: Element* Vector;/存储向量 int Max size, Currentsize;/最大与当前个数
} template class datalist { public: datalist ( int MaxSz = DefaultSize ) : //构造函数 MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } void swap ( Element & x, //对换 Element & y ) { Element temp = x; x = y; y = temp; } private: Element * Vector; //存储向量 int MaxSize, CurrentSize; //最大与当前个数 }
插入排序( Insert Sorting) 插入排序的基本方法是:每步将一个待排序的对 象,按其关键码大小,插入到前面已经排好序的 组对象的适当位置上,直到对象全部插入为止。 直接插入排序( nsert Sort 直接插入排序的基本思想是:当插入第(≥1) 个对象时,前面的Ⅵ0,Ⅵ11,…,v1已经排好 序。这时,用v的关键码与v1,vi21,…的 关鍵码顺序进行比较,找到插入位置即将叫插 入,原来位置上的对象向后顺移
插入排序 (Insert Sorting) 直接插入排序的基本思想是：当插入第i (i 1) 个对象时，前面的V[0], V[1], …, v[i-1]已经排好 序。这时，用v[i]的关键码与v[i-1], v[i-2], …的 关键码顺序进行比较，找到插入位置即将v[i]插 入，原来位置上的对象向后顺移。 插入排序的基本方法是：每步将一个待排序的对 象，按其关键码大小，插入到前面已经排好序的 一组对象的适当位置上，直到对象全部插入为止。 直接插入排序 (Insert Sort)
各 趟 排 21 25//49 25 608 序 012345 结 果 =1目 49 25 6(8 25 2 3 5 temp 49 i=2 2125 08 012345 tem
各 趟 排 序 结 果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 25 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2