1、n 概述概述n 插入排序插入排序n 交换排序交换排序n 选择排序选择排序n 归并排序归并排序n 基数排序基数排序n 外部排序外部排序n 小结小结概述概述n 排序排序 ： 将一组杂乱无章的数据按一定的规律顺将一组杂乱无章的数据按一定的规律顺次排列起来。次排列起来。 n 数据表数据表 (datalist): 它是待排序数据对象的有限它是待排序数据对象的有限集合。集合。n 关键字关键字 (key): 通常数据对象有多个通常数据对象有多个 属性域属性域 ，即，即多个数据成员组成，其中有一个属性域可用来多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。区分对象，作为排序依据
2、。该域即为关键字。每个数据表用哪个属性域作为关键字，要视具每个数据表用哪个属性域作为关键字，要视具体的应用需要而定。即使是同一个表，在解决体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键字。不同问题的场合也可能取不同的域做关键字。n 主关键字主关键字 : 如果在数据表中各个对象的关键字如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字。按照主关互不相同，这种关键字即主关键字。按照主关键字进行排序，排序的结果是唯一的。键字进行排序，排序的结果是唯一的。n 次关键字次关键字 : 数据表中有些对象的关键字可能相数据表中有些对象的关键字可能相同，这种关键字称为次关
3、键字。按照次关键字同，这种关键字称为次关键字。按照次关键字进行排序，排序的结果可能不唯一。进行排序，排序的结果可能不唯一。n 排序算法的稳定性排序算法的稳定性 : 如果在对象序列中有两个如果在对象序列中有两个对象对象 ri和和 rj， 它们的关键字它们的关键字 ki = kj， 且在排且在排序之前，对象序之前，对象 ri排在排在 rj前面。如果在排序之后前面。如果在排序之后，对象，对象 ri仍在对象仍在对象 rj的前面，则称这个排序方的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的法是稳定的，否则称这个排序方法是不稳定的。n 内排序与外排序内排序与外排序 : 内排序是指在排序期间
4、数据内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存，必须根据排序过程的要求，不断在内、外存之间移动的排序。存之间移动的排序。n 排序的时间开销排序的时间开销 : 排序的时间开销是衡量算法排序的时间开销是衡量算法好坏的最重要的标志。好坏的最重要的标志。 排序的时间开销可用算排序的时间开销可用算法执行中的法执行中的 数据比较次数数据比较次数 与与 数据移动次数数据移动次数 来衡来衡量量 。各节给出算法运行时间代价的大略估
5、算一。各节给出算法运行时间代价的大略估算一般都般都 按平均情况按平均情况 进行估算。对于那些进行估算。对于那些 受对象关受对象关键字序列初始排列及对象个数影响较大的键字序列初始排列及对象个数影响较大的 ， 需需要要 按最好情况按最好情况 和和 最坏情况最坏情况 进行估算进行估算 。n 静态排序静态排序 : 排序的过程是对数据对象本身进排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放到合适的位置。这时，数据对象一般都存放在一个顺序的表中。在一个顺序的表中。n 动态排序动态排序 : 给每个对象增加一个链接
6、指针，给每个对象增加一个链接指针，在排序的过程中不移动对象或传送数据，仅在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。序，从而达到排序的目的。n 算法执行时所需的附加存储算法执行时所需的附加存储 : 评价算法好坏评价算法好坏的另一标准。的另一标准。n 静态排序过程中所用到的数据表类定义，体静态排序过程中所用到的数据表类定义，体现了抽象数据类型的思想。现了抽象数据类型的思想。待排序数据表的类定义待排序数据表的类定义#ifndef DATALIST_H#define DATALIST_H#include c
7、onst 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 ) key = x; /修改Element int operator = ( Type int operator != ( Type int op
8、erator key x ); int operator = ( Type template class datalist public:datalist ( int MaxSz = DefaultSize ) : /构造函数MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSz; void swap ( Element x = y; y = temp; private:Element * Vector; /存储向量int MaxSize, CurrentSize; /最大与当前个数插入排序插入排序 (Insert Sorti
9、ng)n 直接插入排序的基本思想是：当插入第直接插入排序的基本思想是：当插入第 i (i 1) 个对象时，前面的个对象时，前面的 V0, V1, , vi-1已经排好已经排好序。这时，用序。这时，用 vi的关键字与的关键字与 vi-1, vi-2, 的的关键字顺序进行比较，找到插入位置即将关键字顺序进行比较，找到插入位置即将 vi插插入，原来位置上的对象向后顺移。入，原来位置上的对象向后顺移。插入排序的基本方法是：每步将一个待排序的对插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止一组对象的适当位置上，直到对象全部插入为止。直接插入排序直接插入排序 (Insert Sort)各趟排序结果21 25 49 25* 16 080 1 2 3 4 50 1 2 3 4 5 temp21 25 49 25* 16 08 25i = 10 1 2 3 4 5 temp21 25 49 25* 16 08 49i = 2
