数据库结构PPT演示文稿

《数据库结构PPT演示文稿》由会员分享，可在线阅读，更多相关《数据库结构PPT演示文稿（49页珍藏版）》请在金锄头文库上搜索。

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

2、到大)或递减(由大到小)的次序重新排列。 排序码(Sort Key)：作为排序依据的关键字。,有序表： 无序表：,升序表正序表： 降序表逆序表：,一、概念,稳定排序：键值相同的记录，排序后相对次序总能保持不变。 不稳定排序：键值相同记录排序前后相对次序不能保持不变。,待排序列： 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）移动：将记录从一个位置移动到另一个位置。 时间开销主要指关键字的比较次数和记录的移动次数。 当键值是字串时，比较要占用较多的时间； 当记录很大时，交换记录时移动要占较多时间。 比较一般都需要，但移动可改变存储方式来避免。,二、时空分析,7.2 插入排序,基本思想： 依次将待排记录插

4、入到有序区适当位置，直到全部记录插入完毕。 初始有序区只有一个元素。,一、基本思想,每次将无序区第1条记录插入到有序区适当位置。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。 初始取第1条记录为有序区，其它记录为无序区。 有序区也可从数据表的尾部生成 。,7.2.1 直接插入排序(Straight Insertion Sort),二分插入 二路插入,初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 65）49 （1

5、3 38 49 49 65 97）,例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较少的情况,有监视哨？,一、基本思想,排序表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；初始增量d1较大，分组较多(每组的记录数少)，以后增量逐渐减少，分组减少(每

6、组的记录数增多)，直到最后增量为1(d1d2dt=1)，所有记录放为同一组，再整体进行一次直接插入排序。 又称“缩小增量排序”(Diminishing Increment Sort)。,7.2.2 希尔排序,例 对(49, 38, 65, 97, 76, 13, 27, 49)希尔排序。,三、效率分析,时间：O(nlog2n)和O(n2)之间，比如O(n1.3) ，优于直接插入 其一，加速原理。相隔为增量的记录一组，组内移动一位，对原序列则移动若干位，加速向目标位置移动。开始时无序程度大，增量大，加速快；以后每个增量排序后，有序度提高一些，增量缩小，加速减缓。 其二，基本有序和小规模原理。开始

7、时增量大，分组多，组内记录少，组内直接插入快；后来增量缩小，分组少，组内记录多，但有序性提高了，排序也较快。 不稳定：组内“相邻”移动，原序列则跳跃移动,7.3 交换排序,基本思想： 每次比较两个待排序的记录，如果关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。 特点：键值较大的记录向排序表的一端移动，键值较小的记录向另一端移动。,一、基本思想,设排序表垂直放置，每个记录看作重量为键值的气泡；根据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。 每一趟一个“最轻”的气泡冒到顶部上升法。 也可从上向下扫描，这时每一趟

8、是一个“最重”的气泡沉到底部下沉法。 每次交换时，其中一个总沿着最终方向，另一个则未必(取决于上升法还是下降法)。,7.3.1 冒泡排序(Bubble Sort),例：对(49, 38, 65, 97, 76, 13, 27, 49)冒泡排序。,时间： 最好：初始正序，一趟排序，比较n-1次，移动0： Cmin=n-1=O(n)，Mmin=0： 最坏：初始逆序，n-1趟排序，每趟比较n-i次，每次比较3次移动： 平均： O(n2) 辅助空间1，用于交换(用R0代替)。 稳定：相邻记录比较和交换。 可用于链表(下沉法),三、效率分析,一、基本思想,任选一记录作基准，其它记录与之比较，小于等于放基

9、准前面；大于等于放基准后面。 一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列进行同样处理，直至每组只有1个记录，全部记录有序。 又称划分交换排序 可看成冒泡排序的改进：记录的比较和交换从两端向中间进行，较大的记录每次交换到较后位置，较小的交换到较前位置，每次移动距离较远，总的比较和移动次数较少。 是目前为止所有内排序中速度最快的一种。,7.3.2 快速排序(Quick Sorting),例，对(49, 38, 65, 97, 76, 13, 27, 49)快速排序,快速排序的判定树： 树根表示基准，左右子树表示划分的两个区间，每个子区间继续用子二叉树表示。,一 趟 划 分,

10、97,49,27,65,13,38,76,49,初始,j向左扫描,i向右扫描,演示：基准最后再放入,时间： 最好：每次划分两侧大致相等，判定树高log2n+1 ， Cmin n(log2n+1)=O(nlog2n) 最坏：每次划分一侧空，剩下另一侧，判定树为单枝树，蜕化为冒泡排序 ： 平均： O(nlog2n) 移动次数不大于比较的次数 辅助空间为栈，深度最好O(log2n)，最坏O(n) 。 不稳定：两头比较和交换，可改变相同键值记录的相对位置,三、效率分析,7.4 选择排序(Selection Sort),基本思想： 每一趟从待排记录中选关键字最小(或最大)的记录，顺序放在已排序的子序列的

11、最后(或最前)，直到全部记录排完,一、基本思想,所有记录组成初始无序区，每趟都从无序区中选出键值最小的记录，与无序区第一个记录交换，有序区增加了一个记录。n1趟排序后，整个排序表就全部有序了。,7.4.1 直接选择排序(Straight Selection Sort),与直接插入相比：总比较次数多，但移动次数少。,树型选择 堆选择,例，对(49, 38, 65, 97, 76, 13, 27, 49)直接选择排序,三、效率分析,时间： n-1趟，每趟都找最小，总比较次数： 最好：初始正序，无移动，Mmin=0，Cmin=O(n2) 最坏：初始反序，Mmax=3(n-1) ，Cmax=O(n2)

12、 平均：O(n2) 辅助空间1，用于交换 不稳定：有不相邻记录交换 可用于链表,直接选择排序时，从n个键值中找最小比较n1次，剩下的找次小比较n2次，再找第三小比较n3次，总比较次数为： (n1)+(n2)+3+2+1= n(n1)/2,7.4.2 树形选择排序(Tree Selection Sort),实际上，除第一次的n1次比较外，后面各次比较中很多在前面已经做过，但结果没有保留，所以在以后又重复进行。,n个记录两两比较，得到 n/2 个较小者。然后再两两比较。如此重复，直至选出键值最小的记录为止。如果某组只有一个记录，则轮空，直接进入下一轮比较。 这个过程可用一棵完全二叉树来表示，故称树

13、形选择排序 该过程又象锦标赛，两两决胜负，最后决出冠军，故又称锦标赛排序(Tournament Sort)。,49,13,13,65,97,39,38,13,38,38,65,76,13,27,27,例：对(49, 38, 65, 97, 76, 13, 27, 49)树形选择排序。,76,27,27,例：对(68, 15, 45, 52, 7, 53, 14)树形选择排序,叶子数n的完全二叉树深度为 log2n +1 第一次n1次比较，以后每次最多log2n 次，总时间不超过(n1)+n log2n =O(nlog2n) 稳定,增加n1个单元保存结果，共2n1个 排序结果另外存储 与+的比较

14、实际多余,一、定义,7.4.3 堆排序(Heap Sort),巧妙的树形选择排序，不需专门设立树。 将R1到Rn看成完全二叉树的顺序存储结构，利用双亲和孩子间的内在关系来选择关键字最小（或最大）的记录。,1）堆是一棵完全二叉树，任一结点关键字小于等于（或大于等于）其孩子结点的关键字。 2）n个关键字序列K1, K2, , Kn称为堆，当且仅当该序列满足： KiK2i且KiK2i+1 (1i n/2) 或者 KiK2i且KiK2i+1 (1i n/2),小根堆 大根堆,不是堆,小根堆,大根堆,不是堆,堆中任一棵子树也是堆,为保证时间性能，就要利用已有结果，每次输出堆顶后，剩下元素不是完全重建，应

15、该在原堆上通过某些调整得到； 为保证空间性能，输出的堆顶应利用原有空间，可将它与无序区最后记录交换位置。排序过程中有序区在原记录区的尾部逐步形成并向前扩大，和直接选择排序相反。,二、堆排序基本思想,利用小(大)根堆选取当前无序区关键字最小(大)的记录来实现排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n1个记录再重建为堆，于是便得到次大值。如此反复，直到全部元素输出完。,两个问题： （1）最初如何由一个无序序列建成一个堆？ （2）在输出堆顶元素后，如何调整剩余元素成为一个新的堆？,1、初始堆的建立,把完全二叉树中以每一结点为根的子树都调整为堆。,只有一个结点的树

16、是堆，在完全二叉树中，所有序号in/2的结点都是叶子，以这些结点为根的子树均已是堆。,依次将以序号为n/2, n/21, , 1的结点作为根的子树都调整为堆。,按该次序调整各结点时，其左、右子树均已是堆(不妨将空树亦看作是堆)。,在根、左、右之间“筛选”最大(或最小)者,例，对(1, 2, 9, 11, 4, 6, 8, 10, 16, 5)建初始堆(大根)。,n=10，故从第10/2 =5个结点开始进行调整,2、调整和重建,将堆顶元素与堆最后的元素互换； 将其余的元素筛选成堆；,交换,筛选,交换,筛选,1,10,16,2,11,4,5,例，对(1, 2, 9, 11, 4, 6, 8, 10, 16, 5)建初始堆(大根)。,9,6,8,n=10，故从第10/2 =5个结点开始进行调整,16,1,2,11,10,5,4,9,6,8,第 1 趟重建和调整,11,