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

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

1、概述插入排序交换排序选择排序归并排序基数排序外排序第九章排序概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。排序码(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r

2、[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储:

3、评价算法好坏的另一标准。待排序数据表的类定义#includeconstintDefaultSize=100;templateclassdataList{templateclassElement{friendclassdataList;private:Typekey;//排序码fieldotherdata;//其他数据成员public:Element():key(0),otherdata(NULL){}TypegetKey(){returnkey;}//提

4、取排序码voidsetKey(constTypex){key=x;}//修改Element&operator=//赋值(Element&x){key=x->key;otherdata=x->otherdata;}intoperator==(Element&x){returnkey==x->key;}//判this==xintoperator<=(Element&x){returnkey<=x->key;}//判thisxintoperator<(Element&x){re

5、turnkeykey;}//判this(Element&x){returnkey>x->key;}//判this>x}templateclassdataList{private:Element*Vector;//存储向量intMaxSize,CurrentSize;//最大与当前个数public:datalist(intMaxSz=DefaultSize):MaxSize(Maxsz),CurrentSize(0){Vector=newElement<

6、Type>[MaxSz];}voidsort();//排序voidswap(Element&x,//对换Element&y){Elementtemp=x;x=y;y=temp;}}插入排序(InsertSorting)基本思想是:当插入第i(i1)个对象时,前面的V[0],V[1],…,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。基本方法是:每步将一个待排序的对象,按其排序码大小,插

7、入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。直接插入排序(InsertSort)各趟排序结果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=221254925*1608012345012345temp21254925*1608i=4012345temp21254925*1608i=5i=325*16081649161621254925*1608012345012345temp21254925*08i=4时的排序过程

8、012345temp21254925*完成160816i=4j=3i=4j=22525*161621254925*08012345012345temp214925*08012345temp21254925*160816162521i=