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

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

ID:52181603

大小:876.50 KB

页数:46页

时间:2020-04-02

插入排序交换排序选择排序归并排序基数排序.ppt_第1页
插入排序交换排序选择排序归并排序基数排序.ppt_第2页
插入排序交换排序选择排序归并排序基数排序.ppt_第3页
插入排序交换排序选择排序归并排序基数排序.ppt_第4页
插入排序交换排序选择排序归并排序基数排序.ppt_第5页
资源描述:

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

1、插入排序交换排序选择排序归并排序基数排序第九章排序排序问题定义给定一组纪录R1,R2,········,Rn其关键码分别为k1,k2,········,kn,将这组纪录重新排成顺序为Rp1,Rp2,········,Rpn的一个序列,使其关键码具有不减顺序kp1≤kp2≤········≤kpn.不同的纪录可以具有相同的关键码。稳定的排序:关键码相同的纪录在排序前和排序后的次序保持不变。约定:关键码用整数代替排序的基本操作比较比较关键码的大小。移动将纪录从一个位置移到另一个位置。排序方法的分类内部排序不

2、用外设外部排序插入,交换,选择,归并,计数等排序法复杂度O(n2)O(nlogn)等排序法静态排序,动态排序原始记录#defineMaxDataSize100templatestructData{Telement;intkey;Data&operator=(constData&a);intoperator<(constData&a,constData&b){returna.key

3、ta&);};templateclassArray//array.h通用数组抽象数组类型{T*alist;intsize;public:Array(ints=50);//构造函数Array(constArray&X);//拷贝构造函数~Array(){delete[]element;}//析构函数Array&operator=(constArray&X);T&operator[](inti);operatorT*()const;intArraySize()cons

4、t;//取数组长voidResize(intsz);//数组长重定义friendostream&operator<<(ostream&,constArray&);};待排序原始记录数组的输入templatevoidInputDataList(Array&L,intn)for(inti=1;i>L[i];}Array>L;InputDataList(L,50);一、插入排序逐个

5、将纪录插入到已排好次序的有序表中得到一个新的有序表。1.直接插入排序最大时间复杂度O(n2)=O(n2/2)+O(n2/2)n-1比较∑i=n(n-1)/2次i=1n-1移动∑(i+2)=(n+4)(n-1)/2i=1最小时间复杂度O(n)不移动4938659776132749494938496549659738496576971338496576972738496576971327384949657697元素个数n越小越好,源序列排序度越高越好2.折半插入排序用折半法比较查找到适当的位置再插入减少比较

6、次数不减少移动次数最坏时间复杂度O(nlogn)+O(n2/2)=O(n2)3.2路插入排序4938659776132749494938496538496597384965769738496576971338496576971327384949657697132738当第一个数据序列中间位置时减少移动次数不减少比较次数复杂性O(n2)FinalFirst4.表插入排序静态链表不移动012345678Maxint493865977613274910Maxint4938659776132749201Maxi

7、nt49386597761327492310Maxint493865977613274923140Maxint493865977613274923140Maxint4938659776132749231504Maxint49386597761327496315042Maxint493865977613274963150472Maxint49386597761327496815047235.链表插入排序动态链表不移动1327384949657697∧6.希尔排序ShellSort缩小增量排序Diminis

8、hingIncrementSort基本思想:先将待排纪录分成若干子列分别用直接插入法排序,再对全体纪录用直接插入法排序。理论根据:直接排序序列越短越好,源序列的排序度越好效率越高。ShellSort取dlta[k]=5,3,2,14938659776132749554一趟排序结果:1327495544938659776二趟排序结果:1344938274955659776三趟排序结果:4132738494955657697//一趟ShellS

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

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

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