《《数据库结构》PPT课件.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（13 38 49 49 65 97）,例1：对(49,38,13,76,65,97,27,4
5、9)直接插入排序。,三、效率分析,时间：最好：正序，n-1趟插入，每趟比较1次，移动0次：Cmin=n-1=O(n)，Mmin=0最坏：逆序，每趟比较i-1次，移动i-1次。平均：O(n2)空间：一个辅助空间，用于交换(或监视哨)。稳定：相邻元素比较和移动可用于链表适用于基本(正向)有序或n较少的情况,有监视哨？,一、基本思想,排序表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；初始增量d1较大，分组较多(每组的记录数少)，以后增量逐渐减少，分组减少(每组的记录数增多)，直到最后增量为1(d1d2dt=1)，所有记录放为同一组，再整体进行一次直接插入排序。又称“缩小增量排序”
6、(Diminishing Increment Sort)。,7.2.2 希尔排序,例 对(49,38,65,97,76,13,27,49)希尔排序。,三、效率分析,时间：O(nlog2n)和O(n2)之间，比如O(n1.3)，优于直接插入其一，加速原理。相隔为增量的记录一组，组内移动一位，对原序列则移动若干位，加速向目标位置移动。开始时无序程度大，增量大，加速快；以后每个增量排序后，有序度提高一些，增量缩小，加速减缓。其二，基本有序和小规模原理。开始时增量大，分组多，组内记录少，组内直接插入快；后来增量缩小，分组少，组内记录多，但有序性提高了，排序也较快。不稳定：组内“相邻”移动，原序列则跳跃
7、移动,7.3 交换排序,基本思想：每次比较两个待排序的记录，如果关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。特点：键值较大的记录向排序表的一端移动，键值较小的记录向另一端移动。,一、基本思想,设排序表垂直放置，每个记录看作重量为键值的气泡；根据轻上重下原则，从下往上扫描，违反本原则的轻气泡，向上“飘浮”，如此反复，直到任何两个气泡都是轻上重下为止。每一趟一个“最轻”的气泡冒到顶部上升法。也可从上向下扫描，这时每一趟是一个“最重”的气泡沉到底部下沉法。每次交换时，其中一个总沿着最终方向，另一个则未必(取决于上升法还是下降法)。,7.3.1 冒泡排序(Bubble Sor
8、t),例：对(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代替)。稳定：相邻记录比较和交换。可用于链表(下沉法),三、效率分析,一、基本思想,任选一记录作基准，其它记录与之比较，小于等于放基准前面；大于等于放基准后面。一趟排序后，左子序列小于等于基准，右子序列大于等于基准。对两子序列进行同样处理，直至每组只有1个记录，全部记录有序。又称划分交换排序可看成冒泡排序的改进：记录的
9、比较和交换从两端向中间进行，较大的记录每次交换到较后位置，较小的交换到较前位置，每次移动距离较远，总的比较和移动次数较少。是目前为止所有内排序中速度最快的一种。,7.3.2 快速排序(Quick Sorting),例，对(49,38,65,97,76,13,27,49)快速排序,快速排序的判定树：树根表示基准，左右子树表示划分的两个区间，每个子区间继续用子二叉树表示。,一 趟 划 分,97,49,27,65,13,38,76,49,初始,j向左扫描,i向右扫描,演示：基准最后再放入,时间：最好：每次划分两侧大致相等，判定树高log2n+1，Cmin n(log2n+1)=O(nlog2n)最坏
10、：每次划分一侧空，剩下另一侧，判定树为单枝树，蜕化为冒泡排序：平均：O(nlog2n)移动次数不大于比较的次数 辅助空间为栈，深度最好O(log2n)，最坏O(n)。不稳定：两头比较和交换，可改变相同键值记录的相对位置,三、效率分析,7.4 选择排序(Selection Sort),基本思想：每一趟从待排记录中选关键字最小(或最大)的记录，顺序放在已排序的子序列的最后(或最前)，直到全部记录排完,一、基本思想,所有记录组成初始无序区，每趟都从无序区中选出键值最小的记录，与无序区第一个记录交换，有序区增加了一个记录。n1趟排序后，整个排序表就全部有序了。,7.4.1 直接选择排序(Straigh
11、t Selection Sort),与直接插入相比：总比较次数多，但移动次数少。,树型选择堆选择,例，对(49,38,65,97,76,13,27,49)直接选择排序,三、效率分析,时间：n-1趟，每趟都找最小，总比较次数：最好：初始正序，无移动，Mmin=0，Cmin=O(n2)最坏：初始反序，Mmax=3(n-1)，Cmax=O(n2)平均：O(n2)辅助空间1，用于交换不稳定：有不相邻记录交换可用于链表,直接选择排序时，从n个键值中找最小比较n1次，剩下的找次小比较n2次，再找第三小比较n3次，总比较次数为：(n1)+(n2)+3+2+1=n(n1)/2,7.4.2 树形选择排序(Tre
12、e Selection Sort),实际上，除第一次的n1次比较外，后面各次比较中很多在前面已经做过，但结果没有保留，所以在以后又重复进行。,n个记录两两比较，得到 n/2 个较小者。然后再两两比较。如此重复，直至选出键值最小的记录为止。如果某组只有一个记录，则轮空，直接进入下一轮比较。这个过程可用一棵完全二叉树来表示，故称树形选择排序该过程又象锦标赛，两两决胜负，最后决出冠军，故又称锦标赛排序(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)树形选择排序。,7
13、6,27,27,例：对(68,15,45,52,7,53,14)树形选择排序,叶子数n的完全二叉树深度为 log2n+1第一次n1次比较，以后每次最多log2n 次，总时间不超过(n1)+n log2n=O(nlog2n)稳定,增加n1个单元保存结果，共2n1个排序结果另外存储与+的比较实际多余,一、定义,7.4.3 堆排序(Heap Sort),巧妙的树形选择排序，不需专门设立树。将R1到Rn看成完全二叉树的顺序存储结构，利用双亲和孩子间的内在关系来选择关键字最小（或最大）的记录。,1）堆是一棵完全二叉树，任一结点关键字小于等于（或大于等于）其孩子结点的关键字。2）n个关键字序列K1,K2,
14、Kn称为堆，当且仅当该序列满足：KiK2i且KiK2i+1(1i n/2)或者KiK2i且KiK2i+1(1i n/2),小根堆大根堆,不是堆,小根堆,大根堆,不是堆,堆中任一棵子树也是堆,为保证时间性能，就要利用已有结果，每次输出堆顶后，剩下元素不是完全重建，应该在原堆上通过某些调整得到；为保证空间性能，输出的堆顶应利用原有空间，可将它与无序区最后记录交换位置。排序过程中有序区在原记录区的尾部逐步形成并向前扩大，和直接选择排序相反。,二、堆排序基本思想,利用小(大)根堆选取当前无序区关键字最小(大)的记录来实现排序。首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n1
15、个记录再重建为堆，于是便得到次大值。如此反复，直到全部元素输出完。,两个问题：（1）最初如何由一个无序序列建成一个堆？（2）在输出堆顶元素后，如何调整剩余元素成为一个新的堆？,1、初始堆的建立,把完全二叉树中以每一结点为根的子树都调整为堆。,只有一个结点的树是堆，在完全二叉树中，所有序号in/2的结点都是叶子，以这些结点为根的子树均已是堆。,依次将以序号为n/2,n/21,1的结点作为根的子树都调整为堆。,按该次序调整各结点时，其左、右子树均已是堆(不妨将空树亦看作是堆)。,在根、左、右之间“筛选”最大(或最小)者,例，对(1,2,9,11,4,6,8,10,16,5)建初始堆(大根)。,n=
16、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,1,2,10,4,5,4,9,6,8,第 2 趟重建和调整,建堆 n/2 筛选，重建n1次筛选，每次筛选双亲和孩子比较和移动，不超过深度，时间复杂度(n/2+n1)O(log2n)=O(nlog2n)。辅助空间为1(供交
17、换用)，空间复杂度为O(1)。不稳定，如(2,1,2),四、效率分析,一、二路归并排序基本思想,初始排序表看成n个长度为1的有序子表，两两归并，得到 n/2 个有序的子表(当n为奇数时，归并后仍有一个长度为1的子表)；再把这些有序子表两两归并，如此反复，直到最后得到一个长度为n的有序表为止。,7.5 归并排序(Merging Sort),利用“归并”技术来进行排序，所谓归并是指将若干个已排序的子表合并成一个有序表。,例 对(49,38,65,97,76,13,49)二路归并排序。,比较：归并时子表不断变大；快排时子表不断化小。,7,63,16,3,88,R：,R1：,54,16,79,例两子表
18、合并,三效率分析,子表长度不断加倍，1n，归并趟数为log2n；每趟归并比较次数移动次数，后者为O(n)；总时间复杂度O(nlog2n)。辅助空间为数组R1，空间复杂度O(n)键值相同记录顺序复制，不改变相对位置，故是稳定的。可在链表上实现,7.6 分配排序,利用关键字结构，通过“分配”和“收集”实现排序无需比较关键字。可分为箱排序和基数排序两类。,7.6.1 箱排序、桶排序(Bin Sort、Bucket Sort),设置若干箱子，扫描待排记录R1、R2、Rn，把关键字等于k的记录全都装入到第k个箱子(分配)，然后，按序号依次将各非空的箱子首尾连接起来(收集)。,例，扑克牌按面值A2JQK排
19、序(不分花色)，设置13个“箱子”，依次将每张牌按面值放入相应的箱子里，然后依次将箱子首尾相接，就得到按面值递增序排列的一副牌。,箱子个数m取决于关键字的取值范围。分配时间O(n)，收集时间O(m+n)（若用链表，则O(m)），所以箱排序时间O(m+n)。若关键字的取值范围很大，如m=O(n2)，则效率很低。,7.6.2 基数排序(Radix Sort),多关键字排序：低位优先，高位优先?每趟箱子共用，每趟排序前清空箱子（除第一趟外）箱子的数据按队列存放 箱子内数据个数可变，适合链表实现链式基数排序,将关键字看成多个分量组成，从低到高依次对关键字的各分量进行箱排序，每趟所需箱子数就是基数。,时
20、间：链表初始化O(n)，清箱O(r)，收集O(r)，分箱O(n)，一趟总O(n+r)，d趟总O(d(n+r)O(n)。空间：结点指针O(n)，箱子头尾指针O(r)，总O(n+r)稳定：分配和收集不改变相同键值的相对位置。,例对(91,46,85,15,92,35,31,22)基数排序,0,1,2,3,4,5,6,7,8,9,91,46,85,15,92,35,31,22,收集：91 31 92 22 85 15 35 46,0,1,2,3,4,5,6,7,8,9,91,31,92,22,85,15,35,46,收集：15 22 31 35 46 85 91 92,分配(按个位),分配(按十位),7.7 内排序的比较和选择,简单排序(直接插入、直接选择、冒泡排序等)每次只对相邻元素比较，前进步伐慢，时间耗费大，为O(n2)，但一些特殊情况却可取得很好效果；效率高的算法每次比较产生的作用不仅仅局限于被比较的两个元素，而是多个甚至一半左右，但它们对数据量小的情况并不一定合适。,综合考虑下列因素：(1)待排序的记录数目。(2)记录本身信息量的大小。(3)关键字的结构及其分布情况。(4)对排序稳定性的要求。(5)语言工具的条件。(6)算法本身的难易程度。(7)辅助空间的大小等。,
