数据结构课件第十章.ppt

该【数据结构课件第十章 】是由【相惜】上传分享，文档一共【59】页，该文档可以免费在线阅读，需要了解更多关于【数据结构课件第十章 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。、排序是计算机内经常进行的一种操作,其目的是将一组“无序〞的记录序列调整为“按关键字有序〞的记录序列。52,49,80,36,14,58,61,23,97,7514,23,36,49,52,58,61,75,80,97一般情况下,假设含n个记录的序列为{R1,R2,……,Rn}其相应的关键字序列为{K1,K2,……,Kn}这些关键字相互之间可以进行比较,即在它们之间存在这样一个关系:Kp1<=Kp2<=…<=Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn}的操作称作排序3精选课件2、关键字数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可以用来区分对象,作为排序依据,称为关键字。关键字与记录之间是一对一的关系称主关键字关键字与记录之间是一对多的关系称次关键字4精选课件3、排序的目的是什么?——便于查找4、排序算法的好坏如何衡量?时间效率——排序速度〔即排序所花费的全部比较次数〕空间效率——占内存辅助空间的大小稳定性——假设两个记录A和B的关键字相等,但排序后A,B的先后次序保持不变,那么称这种排序算法是稳定的。5精选课件5、什么叫内部排序?什么叫外部排序——假设待排序记录都在内存中,称内部排序——假设待排序记录一局部在内存,一局部在外存,那么称为外部排序。注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入内存,显然外部排序要复杂得的多。内部排序和外部排序的不同在于能否一次处理完所有数据6精选课件6、排序主要做的工作:比较+?——按排序的规那么不同,可分为5类:插入排序交换排序〔重点是快速排序〕选择排序归并排序基数排序d=关键字的位数(长度)——按排序算法的时间复杂度不同,可分为3类:简单的排序算法:时间效率低,O(n2)先进的排序算法:时间效率高,O(nlog2n)基数排序算算法:时间效率高,O(d×n):插入排序有多种具体实现算法:1)直接插入排序2)折半插入排序3)希尔排序每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。简言之,边插入边排序,保证子序列中随时都是排好序的。9精选课件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】在已形成的有序表中线性查找,并在适当位置插入,把原来位置上的元素向后顺移。最简单的排序法!10精选课件