数据结构 课件 排序.ppt

《数据结构 课件 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

3、一标准。5待排序数据表的类定义#includeconstintDefaultSize=100;templateclassElement{//数据表元素定义public:Tkey;//排序码Element&operator=(Element&x){key=x.key;otherdata=x.otherdata;return*this;}6booloperator==(Element&x){returnkey==x.key;}//判*this与x相等booloperator<=(Element&x){

4、returnkey<=x.key;}//判*this小于或等于xbooloperator>=(Element&x){returnkey>=x.key;}//判*this大于或等于xbooloperator>(Element&x){returnkey>x.key;}//判*this大于xbooloperator<(Element&x){returnkeyclassdataList{//数据表类定义private:Element*Vector;//存储排序元素的向量

5、intmaxSize;//向量中最大元素个数intcurrentSize;//当前元素个数public:datalist(intmaxSz=DefaultSize)://构造函数maxSize(maxSz),currentSize(0){Vector=newElement[maxSize];}intLength(){returncurrentSize;}//取表长度8voidSwap(Element&x,Element&y){Elementtemp=x;x=y;y=temp;}Element&operator[](inti)//取

6、第i个元素{returnVector[i];}intPartition(constintlow,constinthigh);//快速排序划分};9插入排序(InsertSorting)基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素全部插入为止。基本思想是:当插入第i(i≥1)个元素时，前面的V[0],V[1],…,V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较，插入位置即将V[i]插入，原来位置上的元素向后顺移。直接插入排序(InsertSort)1

7、0各趟排序结果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=211012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*1608081221254925*1608012345i=4时的排序过程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=2132516012345temp2149

8、25*08162525*1621254