概述插入排序交换排序选择排序归并排序基数排序外排序小结.ppt

《概述插入排序交换排序选择排序归并排序基数排序外排序小结.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、概述插入排序交换排序选择排序归并排序基数排序外排序小结第九章排序概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。关键码(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键码。主关键码:如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排

2、序，排序的结果是唯一的。次关键码:数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键码k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须

3、根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。静态排序:排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。动态排序:给每个对象增加一个链接指针，在排序的过程中不移动对

4、象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。算法执行时所需的附加存储:评价算法好坏的另一标准。静态排序过程中所用到的数据表类定义，体现了抽象数据类型的思想。待排序数据表的类定义#ifndefDATALIST_H#defineDATALIST_H#includeconstintDefaultSize=100;templateclassdatalist{templateclassElement{private:T

5、ypekey;//关键码fieldotherdata;//其它数据成员public:Element():key(0),otherdata(NULL){}TypegetKey(){returnkey;}//提取关键码voidsetKey(constTypex){key=x;}//修改Element&operator=//赋值(Element&x){this=x;}intoperator==(Type&x)//判this==x{return!(this

6、

7、x

8、rator!=(Type&x)//判this!=x{returnthis

9、

10、xx);}intoperator>=(Type&x)//判thisx{return!(thisx;}}templateclassdatalist{public:datalist(intMaxSz=DefaultSiz

11、e)://构造函数MaxSize(Maxsz),CurrentSize(0){Vector=newElement[MaxSz];}voidswap(Element&x,//对换Element&y){Elementtemp=x;x=y;y=temp;}private:Element*Vector;//存储向量intMaxSize,CurrentSize;//最大与当前个数}插入排序(InsertSorting)直接插入排序的基本思想是：当插入第i(i

12、1)个对象时，前面的V[0],V[1],…,v[i-1]已经排好序。这时，用v[i]的关键码与v[i-1],v[i-2],…的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。插入排序的基本方法是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。直接插入排序(InsertSort)各趟排序结果21254925*160