文档介绍：该【《数据库结构》 】是由【相惜】上传分享，文档一共【49】页，该文档可以免费在线阅读，需要了解更多关于【《数据库结构》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。*外排序简介排序就是将一组杂乱无章的数据按一定的规律顺次排列起来。排序的目的是为了方便以后的查找。关键字(key):记录中可用来标识一个记录的数据项或其组合。关键字也简称键,它的值称为键值。(PrimaryKey):可唯一标识记录的关键字,即不同记录该关键字的值不同。次关键字(SecondaryKey):不能唯一标识记录的关键字。排序(Sorting):简单地说,就是将一组记录按关键字域递增(由小到大)或递减(由大到小)的次序重新排列。排序码(SortKey):作为排序依据的关键字。有序表:无序表:升序表/正序表:降序表/逆序表:一、概念稳定排序:键值相同的记录,排序后相对次序总能保持不变。不稳定排序:键值相同记录排序前后相对次序不能保持不变。待排序列:49,38,65,97,76,13,27,49排序后:13,27,38,49,49,65,76,97—稳定?排序后:13,27,38,49,49,65,76,97—不稳定内排序:排序过程全部在内存中进行。外排序:排序过程需要进行内存和外存之间的数据交换。插入排序(直插排序、二分排序、希尔排序)交换排序(冒泡排序、快速排序)选择排序(直选排序、树型排序、堆排序)归并排序(二路归并排序、多路归并排序)分配排序(多关键字排序、基数排序)内排序评价标准:1〕时间;2〕附加空间。3〕算法的稳定性、复杂程度等附加空间一般不大,排序经常执行,时间开销是最重标志。两种根本操作:1〕比较:比较关键字的大小2〕移动:将记录从一个位置移动到另一个位置。时间开销主要指关键字的比较次数和记录的移动次数。当键值是字串时,比较要占用较多的时间;当记录很大时,交换记录时移动要占较多时间。比较一般都需要,但移动可改变存储方式来防止。二、:依次将待排记录插入到有序区适当位置,直到全部记录插入完毕。初始有序区只有一个元素。一、根本思想每次将无序区第1条记录插入到有序区适当位置。随着排序进行,有序区不断扩大,无序区不断缩小。最终无序区为空,有序区包含了全部记录,排序结束。初始取第1条记录为有序区,其它记录为无序区。有序区也可从数据表的尾部生成。(StraightInsertionSort)二分插入二路插入初始:〔49〕3813762749 〔3849〕13762749〔133849〕762749〔13384976〕2749〔1327384965〕49〔133849496597〕例1:对(49,38,13,76,65,97,27,49)直接插入排序。三、效率分析时间:最好:正序,n-1趟插入,每趟比较1次,移动0次: Cmin=n-1=O(n),Mmin=0最坏:逆序,每趟比较i-1次,移动i-1次。平均:O(n2)空间:一个辅助空间,用于交换(或监视哨)。稳定:相邻元素比较和移动可用于链表适用于根本(正向)有序或n较少的情况有监视哨?2ii-1+2一、根本思想排序表分成假设干组,相隔为某个“增量〞的记录为一组,各组内直接插入排序;初始增量d1较大,分组较多(每组的记录数少),以后增量逐渐减少,分组减少(每组的记录数增多),直到最后增量为1(d1>d2>…>dt=1),所有记录放为同一组,再整体进行一次直接插入排序。又称“缩小增量排序〞(DiminishingIncrementSort)。(49,38,65,97,76,13,27,49?)希尔排序。