《数据库结构》PPT课件

《《数据库结构》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章排序7.1基本概念7.2插入排序7.3交换排序7.4选择排序7.5归并排序7.6分配排序7.7内排序的比较和选择7.8*外排序简介排序就是将一组杂乱无章的数据按一定的规律顺次排列起来。排序的目的是为了方便以后的查找。关键字(key)：记录中可用来标识一个记录的数据项或其组合。关键字也简称键，它的值称为键值。7.1基本概念主关键字(PrimaryKey)：可唯一标识记录的关键字，即不同记录该关键字的值不同。次关键字(SecondaryKey)：不能唯一标识记录的关键字。排序(Sorting)：简单

2、地说，就是将一组记录按关键字域递增(由小到大)或递减(由大到小)的次序重新排列。排序码(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—不稳定内排序：排序过程全部在内存中进行。

3、外排序：排序过程需要进行内存和外存之间的数据交换。插入排序(直插排序、二分排序、希尔排序)交换排序(冒泡排序、快速排序)选择排序(直选排序、树型排序、堆排序)归并排序(二路归并排序、多路归并排序)分配排序(多关键字排序、基数排序)内排序评价标准：1）时间；2）附加空间。3）算法的稳定性、复杂程度等附加空间一般不大，排序经常执行，时间开销是最重标志。两种基本操作：1）比较：比较关键字的大小2）移动：将记录从一个位置移动到另一个位置。时间开销主要指关键字的比较次数和记录的移动次数。当键值是字串时，比较要占

4、用较多的时间；当记录很大时，交换记录时移动要占较多时间。比较一般都需要，但移动可改变存储方式来避免。二、时空分析7.2插入排序基本思想：依次将待排记录插入到有序区适当位置，直到全部记录插入完毕。初始有序区只有一个元素。一、基本思想每次将无序区第1条记录插入到有序区适当位置。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。初始取第1条记录为有序区，其它记录为无序区。有序区也可从数据表的尾部生成。7.2.1直接插入排序(StraightInsertionSor

5、t)二分插入二路插入初始：（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)空间：一个辅助空间，用于交换(或监视哨)。稳定：相邻元素比较和移动可用于

6、链表适用于基本(正向)有序或n较少的情况有监视哨？2ii-1+2一、基本思想排序表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；初始增量d1较大，分组较多(每组的记录数少)，以后增量逐渐减少，分组减少(每组的记录数增多)，直到最后增量为1(d1>d2>…>dt=1)，所有记录放为同一组，再整体进行一次直接插入排序。又称“缩小增量排序”(DiminishingIncrementSort)。7.2.2希尔排序例对(49,38,65,97,76,13,27,49)希尔排序。三、效率分析时

7、间：O(nlog2n)和O(n2)之间，比如O(n1.3)，优于直接插入其一，加速原理。相隔为增量的记录一组，组内移动一位，对原序列则移动若干位，加速向目标位置移动。开始时无序程度大，增量大，加速快；以后每个增量排序后，有序度提高一些，增量缩小，加速减缓。其二，基本有序和小规模原理。开始时增量大，分组多，组内记录少，组内直接插入快；后来增量缩小，分组少，组内记录多，但有序性提高了，排序也较快。不稳定：组内“相邻”移动，原序列则跳跃移动7.3交换排序基本思想：每次比较两个待排序的记录，如果关键字的次序与

8、排序要求相反时就交换两者的位置，直到没有反序的记录为止。特点：键值较大的记录向排序表的一端移动，键值较小的记录向另一端移动。一、基本思想设排序表垂直放置，每个记录看作重量为键值的气泡；根据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。每一趟一个“最轻”的气泡冒到顶部－上升法。也可从上向下扫描，这时每一趟是一个“最重”的气泡沉到底部－下沉法。每次交换时，其中一个总沿着最终方向，另一个则未必(取决于