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

《插入排序交换排序选择排序归并排序基数排序.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