数据结构 课件 排序

数据结构 课件 排序

ID:45096074

大小:731.50 KB

页数:140页

时间:2019-11-09

数据结构 课件 排序_第1页
数据结构 课件 排序_第2页
数据结构 课件 排序_第3页
数据结构 课件 排序_第4页
数据结构 课件 排序_第5页
资源描述:

《数据结构 课件 排序》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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

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

3、数据表的类定义#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){returnkey<=x

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

5、最大元素个数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)//取第i个元素{returnVector[i

6、];}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)10各趟排序结果21254925*16080123

7、45012345temp21254925*160825i=1012345temp21254925*160849i=211012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*1608081221254925*1608012345i=4时的排序过程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=2132516012345temp214925*08162525*1621254

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。