数据结构第9章排序.ppt

该【数据结构第9章排序 】是由【相惜】上传分享，文档一共【103】页，该文档可以免费在线阅读，需要了解更多关于【数据结构第9章排序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。?将一组杂乱无章的数据按一定的规律顺次排列起来。??时间效率——排序速度〔即排序所花费的全部比较次数〕空间效率——占内存辅助空间的大小稳定性——假设两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,那么称这种排序算法是稳定的。——便于查找!?什么叫外部排序?——假设待排序记录都在内存中,称为内部排序;——假设待排序记录一局部在内存,一局部在外存,那么称为外部排序。注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。?①顺序排序——排序时直接移动记录;②链表排序——排序时只移动指针;③地址排序——排序时先移动地址,最后再移动记录。注:地址排序中可以增设一维数组来专门存放记录的地址。4精选课件注:大多数排序算法都是针对顺序表结构的(便于直接移动元素)〔顺序表〕的抽象数据类型如何表示?Typedefstruct{//定义每个记录〔数据元素〕的结构KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RecordType;Typedefstruct{//定义顺序表的结构RecordTyper[MAXSIZE+1];//存储顺序表的向量//r[0]一般作哨兵或缓冲区intlength;//顺序表的长度}SqList;#defineMAXSIZE20//设记录不超过20个typedefintKeyType;//设关键字为整型量〔int型〕?——按排序的规那么不同,可分为5类:插入排序交换排序〔重点是快速排序〕选择排序归并排序基数排序d=关键字的位数(长度)——按排序算法的时间复杂度不同,可分为3类:简单的排序算法:时间效率低,O(n2)先进的排序算法:时间效率高,O(nlog2n)基数排序算算法:时间效率高,O(d×n):插入排序有多种具体实现算法:1)直接插入排序2)折半插入排序3)2-路插入排序4)表插入排序5)希尔排序每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。简言之,边插入边排序,保证子序列中随时都是排好序的。7精选课件1)直接插入排序新元素插入到哪里?例1:关键字序列T=〔13,6,3,31,9,27,5,11〕,请写出直接插入排序的中间过程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13,31】,9,27,5,11【3,6,9,13,31】,27,5,11【3,6,9,13,27,31】,5,11【3,5,6,9,13,27,31】,11【3,5,6,9,11,13,27,31】在已形成的有序表中线性查找,并在适当位置插入,把原来位置上的元素向后顺移。最简单的排序法!8精选课件例2:关键字序列T=〔21,25,49,25*,16,08〕,请写出直接插入排序的具体实现过程。*表示后一个25i=121254925***********暂存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解:假设该序列已存入一维数组V[7]中,将V[0]作为缓冲或暂存单元〔Temp〕。那么程序执行过程为:21254925*21初态:164925*25211608完成!时间效率:O(n2)——因为在最坏情况下,所有元素的比较次数总和为〔0+1+…+n-1)→O(n2)。其他情况下还要加上移动元素的次数。空间效率:O〔1〕——因为仅占用1个缓冲单元算法的稳定性:稳定——因为25*排序后仍然在25的后面。对应程序参见教材P265。9精选课件假设设待排序的对象个数为n,那么算法需要进行n-1次插入。最好情况下,排序前对象已经按关键码大小从小到大有序,每趟只需与前面的有序对象序列的最后一个对象的关键码比较1次,移动2次对象。因此,总的关键码比较次数为n-1,对象移动次数为2(n-1)。直接插入排序的算法分析10精选课件