数据结构与算法分析(C++版)下ppt课件

1、四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃数据构造与算法数据构造与算法分析分析(C+版版)课件课件下下四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃第第8讲讲 查找查找第第9讲讲 排序排序第第10讲讲 文件文件第第11讲讲 算法设计与分析算法设计与分析四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃第第8章章 查找查找四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，

2、主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃查找算法的评价目的查找算法的评价目的 查找胜利查找胜利: :最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数 查找失败查找失败: :最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 以顺序表或线性链表表示静态查找表顺序查找顺序查找四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃elem顺序查找过程顺序查找过程假设给定值假设给定值 e=64,要求要求 ST.e

3、lemk = e, 问问: k = ?kk四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表折半查找折半查找 假设以有序表表示静态查找表，那么查找过程可以基于“折半进展四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃elem例如例如: key=64 的查找过

4、程如下的查找过程如下lowhighmidlow mid high midmid = (low+high)/2Low 指示查找区间的下界指示查找区间的下界high 指示查找区间的上界指示查找区间的上界四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二叉排序树二叉排序树二叉查找树二叉查找树四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃1假设它的左子树不空，那么左子假设它的左子树不空，那么左子树上树上 一切结点的值均小于根结点的值一切结点的值均小于根结点的值 二叉排序树或者是一棵

5、空树；或者是具有如下特性的二叉树3它的左、右子树也都分别是二叉它的左、右子树也都分别是二叉 排序树排序树2假设它的右子树不空，那么右子假设它的右子树不空，那么右子树上树上 一切结点的值均大于根结点的值一切结点的值均大于根结点的值四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃503080209010854035252388是二叉排序树是二叉排序树66不不四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二叉排序树的二叉排序树的查找算法查找算法四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 1假设给定值等于根结点的关键字，假

6、设给定值等于根结点的关键字， 那么查找胜利那么查找胜利 2假设给定值小于根结点的关键字，假设给定值小于根结点的关键字， 那么继续在左子树上进展查找那么继续在左子树上进展查找 3假设给定值大于根结点的关键字，假设给定值大于根结点的关键字， 那么继续在右子树上进展查找那么继续在右子树上进展查找否那么否那么: 假设二叉排序树为空，那么查找不胜假设二叉排序树为空，那么查找不胜利利四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃50308020908540358832查找关键字查找关键字50505030403550508090= 50 , 35 , 90 , 95四川大学计算机学

7、院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃51*2*34*5*6*41C13133*2122133132123123n*n2C1n1四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃在查找过程中，生成了一条查找途径在查找过程中，生成了一条查找途径 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点或者或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止 查找胜利查找胜利 查找不胜利查找不胜利四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游

8、洪跃30201040352523fT key = 48fTfT22pfTfTTTTfffp四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃351545504025102030四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值一样的 n个关键字，构造所得的不同形状的各棵二叉排序树的平均查找长 度的值不同，甚至能够差别很大四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃由关键字序列由关键字序列 3，1，2，5，4构

9、造而得的二叉排序树构造而得的二叉排序树由关键字序列由关键字序列 1，2，3，4，5构造而得的二叉排序树构造而得的二叉排序树2134535412ASL =1+2+3+4+5/ 5 = 3ASL =1+2+3+2+3/ 5 = 2.2四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 输入数据，建立二叉查找树的过程535378537865537865175378658717537865091787537865811787095378651517870981四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机

10、学院，主讲教师：游洪跃123111132223323四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二叉平衡树二叉平衡树AVLAVL树树四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 不平衡不平衡 平衡平衡ABCABCDEDE四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃548254821是平衡树是平衡树不是平衡树不是平衡树四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院

11、，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃构造二叉平衡查找树的方法构造二叉平衡查找树的方法在插入过程中，采用平衡旋转技术在插入过程中，采用平衡旋转技术依次插入的关键字为依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃426589642895向左旋转一次继续插入关键字继续插入关

12、键字 9四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃B - 树树四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃B-树是一种树是一种 平衡平衡 的的 多路多路 查找查找 树树 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 在 m 阶的B-树上，每个非终端结点能够含有： n 个关键字 Ki1 in nm n 个指向记录的指针 Di1in n+1 个指向子树的指针 Ai0in多叉树的特性多叉树的特性四川大学计算机学院，主讲教师：游洪

13、跃四川大学计算机学院，主讲教师：游洪跃 非叶结点中的多个关键字均自小至大非叶结点中的多个关键字均自小至大有序陈列，即：有序陈列，即：K1 K2 KnK1 K2 = 0 & elem0elem j; -j); / 从后往前找从后往前找j=i-1插入位置插入位置四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 对于在查找过程中找到的那些关键字大于elemi(=e)的记录，并在查找的同时实现记录向后挪动；for (j=i-1; e elemj; -j); elemj+1 = elemjjelemij= i-1上述循环终了后可以直接进展“插入插入位置插入位置四川大学计算机学院，

14、主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃令 i = 1，3，, n, 实现整个序列的排序。for ( i=1; in; +i ) if (elemi elemi-1) 在在 elem0.i-1中查找中查找elemi的插入位置的插入位置; 插入插入elemi ; 四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 二、希尔排序又称减少增量排序二、希尔排序又称减少增量排序 根本思想：对待排记录序列先作“宏观调整，再作“微观调整。 所谓“宏观调整，指的是，“腾跃式的插入排序。 详细做法为：四川大

15、学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃将记录序列分成假设干子序列，分别对每个子序列进展插入排序。其中，d 称为增量，它的值在排序过程中从大到小逐渐减少，直至最后一趟排序减为 1。例如：将 n 个记录分成 d 个子序列： elem0，elem0+d，elem0+2d， elem0+kd elem1，elem1+d，elem1+2d， elem1+kd elemd-1, elem2d-1, elem3d-1, , elem(k+1)d-1四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：16 25 12 30 47 11 23 36 9 18

16、 31 第一趟希尔排序，设增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃归并排序四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃归归

17、 并并 排排 序序归并排序的过程基于以下根本思想进展： 将两个或两个以上的有序子序列 “归并 为一个有序序列。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m 有序子序列有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃归并排序的算法归并排序的算法假设记录无序序列 Rs.t 的两部分 Rs.(s+t)/2 和 R(s+t)/2+

18、1.t分别按关键字有序，那么利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进展 2-路归并排序。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃快速排序四川大学计算机学院

19、，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃一、起泡排序一、起泡排序假设在排序过程中，记录序列R0.n-1的形状为：第 i 趟起泡排序无序序列R0.n-i有序序列 Rn-i+1.n-1n-i无序序列R0.n-i-1有序序列 Rn-i.n-1比较相邻记录，将关键字最大的记录交换到 n-i 的位置上四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二、一趟快速排序一次划分二、一趟快速排序一次划分目的：找一个记录，以它的关键字作为目的：找一个记录，以它的关键字作为“枢轴，凡其关键字小于枢轴的记录均

20、枢轴，凡其关键字小于枢轴的记录均挪动至该记录之前，反之，凡关键字大于挪动至该记录之前，反之，凡关键字大于枢轴的记录均挪动至该记录之后。枢轴的记录均挪动至该记录之后。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.i-1和Ri+1.t，且 Rj Ri Rk (sji-1) 枢轴 (i+1kt)。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进展比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和

21、 枢轴的关键字进展比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 可见，经过“一次划分 ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t， 之后逐渐减小 high，添加 low，并保证 Rhigh52，和 Rlow52,

22、否那么进展记录的“交换。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃快速排序快速排序 首先对无序的记录序列进展“一次划分，之后分别对分割所得两个子序列“递归进展快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进展快速排序四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃堆排序四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃一、简单项选择择排序一、简单项选择择排序假设排序过程中，待排记录序列的形状为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单项选择择排序从中选出关键字

23、最小的记录有序序列R1.i无序序列 Ri+1.n四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二、堆排序二、堆排序堆是满足以下性质的数列r0, r1, ，rn-1：或或2212iiiirrrr2212iiiirrrr堆的定义堆的定义:(小顶堆)(大顶堆)四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃riR2i+1 r2i+2 假设将该数列视作完全二叉树，那么 r2i+1 是 ri 的左孩子； r2i+2 是 ri 的右孩子。1236276549817355403498例如

24、例如:是堆是堆14不不四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃堆排序即是利用堆的特性对记录序列进展排序的一种排序方法。例如：例如：建大顶堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交换 98 和 12重新调整为大顶堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 经过挑选四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪

25、跃如何如何“建堆？建堆？两个问题两个问题:如何如何“挑选？挑选？四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃所谓“挑选指的是，对一棵左/右子树均为堆的完全二叉树，“调整根结点使整个二叉树也成为一个堆。堆堆挑选挑选四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃98814973556412362740例如例如:是大顶堆是大顶堆12但在 98 和 12 进展互换之后，它就不是堆了，因此，需求对它进展“挑选。98128173641298比较比较比较四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃建堆是一个从下往上进展建堆是一

26、个从下往上进展“挑选的过程。挑选的过程。40554973816436122798例如例如: 排序之前的关键字序列为排序之前的关键字序列为123681734998817355 如今，左/右子树都曾经调整为堆，最后只需调整根结点，使整个二叉树是个“堆即可。98494064361227四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃基基 数数 排排 序序四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃基数排序是一种借助“多关键字排序的思想来实现“单关键字排序的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序四川大学计算机学院，主讲教师

27、：游洪跃四川大学计算机学院，主讲教师：游洪跃多关键字的排序多关键字的排序 n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1,Kid-1) 有序是有序是指：指： 其中其中: K0 : K0 被称为被称为 “最主位关键字最主位关键字Kd-1 被称为被称为 “最次位关键字最次位关键字 对于序列中恣意两个记录 Ri 和 Rj(1ijn) 都满足以下(词典)有序关系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 实现多关键字排序通常有两种作法:最低位优先最低位优

28、先LSDLSD法法最高位优先最高位优先MSDMSD法法四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃最高位优先最高位优先MSDMSD法法先对先对K0K0进展排序，并按进展排序，并按 K0 K0 的不的不同值将记录序列分成假设干子序同值将记录序列分成假设干子序列之后，分别对列之后，分别对 K1 K1 进展排进展排序，序，.， 依次类推，直至最依次类推，直至最后对最次位关键字排序完成为止。后对最次位关键字排序完成为止。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃最低位优先最低位优先LSDLSD法法先对先对 Kd-1 Kd-1 进展排序，然后对进

29、展排序，然后对 Kd-2 Kd-2 进展排序，依次类推，直进展排序，依次类推，直至对最主位关键字至对最主位关键字 K0 K0 排序完成为排序完成为止。止。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如例如: :学生记录含三个关键字学生记录含三个关键字: :系别、班号和班内的序列号，其中以系别、班号和班内的序列号，其中以系别为最主位关键字。系别为最主位关键字。 无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,

30、153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下:四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃链式基数排序链式基数排序假设多关键字的记录序列中，每个关键字的取值范围一样，那么按LSD法进展排序时，可以采用“分配-搜集的方法，其益处是不需求进展关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-搜集的方法进展排序，称作基数排序法。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：对以下这组关键字例如：对

31、以下这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数 取值分别为 0, 1, , 9 “分配 成 10 组，之后按从 0 至 9 的顺序将 它们 “搜集 在一同； 然后按其 “十位数 取值分别为 0, 1, , 9 “分配 成 10 组，之后再按从 0 至 9 的顺序将它们 “搜集 在一同；最后按其“百位数反复一遍上述操作。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储构造，即链式基数排序，详细作法为： 待排序记录以指针相链，构成一个

32、链表；“分配分配 时，按当前时，按当前“关键字位所关键字位所取值，将记录分配到不同的取值，将记录分配到不同的 “链队列链队列 中，每个队列中记录的中，每个队列中记录的 “关键字位关键字位 一一样；样；“搜集时，按当前关键字位取值从搜集时，按当前关键字位取值从小到大将各队列首尾相链成一个链表小到大将各队列首尾相链成一个链表; ;对每个关键字位均反复对每个关键字位均反复 2) 2) 和和 3) 3) 两步。两步。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：p369367167239237230进展第一次分配进展第一次分配进展第一次搜集进展第一次搜集f0 r0f7

33、r7f8 r8f9 r9p230230367 167237367167237368239369 239四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃进展第二次分配进展第二次分配p230237239p230367167237368239f3 r3f6 r6230 237239367 167368367167368进展第二次搜集四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 进展第三次搜集之后便得到记录的有序序列f1 r1p230237239367167368进展第三次分配进展第三次分配f2 r2f3 r3 167230 237239367 36

34、8p167230237239367368四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 基数排序的时间复杂度为O(d(n+rd)其中：分配为O(n) 搜集为O(rd)(rd为“基) d为“分配-搜集的趟数四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃各种排序方法的综合比较各种排序方法的综合比较四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃一、时间性能一、时间性能1. 平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为

35、时间复杂度为 O(n2) O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和简单项选择择排序简单项选择择排序时间复杂度为时间复杂度为 O(n):四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃2. 当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3. 简单项选择择排序、堆排序和归并排简单项选择择排序、堆排序和归并排序的时间性能不随记录序列中关键字的序的时间性能不随记录序列中关键字的分布而改动。分布而改动。 直接插入排序和起泡排序能到达O(n)的时间复杂度， 快速排序的时间性能蜕化为O(n2) 。四川大学计算机学院，主讲教师：游洪跃四川大学计算机

36、学院，主讲教师：游洪跃排序方法的稳定性能排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改动。 2. 当对多关键字的记录序列进展当对多关键字的记录序列进展LSD方法排序时，必需采用稳定的排序方方法排序时，必需采用稳定的排序方法。法。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )假设排序后得到结果 ( 18, 23, 34, 4

37、7, 47, 56, 66, 82 )那么称该排序方法是稳定的;假设排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )那么称该排序方法是不稳定的。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 3. 对于不稳定的排序方法，只需能对于不稳定的排序方法，只需能举出一个实例阐明即可。举出一个实例阐明即可。 4. 快速排序、一切选择排序快速排序、一切选择排序(包括堆排序包括堆排序和希尔排序是不稳定的排序方法。和希尔排序是不稳定的排序方法。例如例如 : 对对 4, 3, 4, 2 进展快速排序，进展快速排序， 得到得到 2, 3, 4, 4 四

38、川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃外外 部部 排排 序序四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃一一. 问题的提出问题的提出 待排序的记录数量很大，不能一次装入内存，那么无法利用前几节讨论的排序方法 ；四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 按可用内存大小，利用内部排序按可用内存大小，利用内部排序 方法，构造假设干方法，构造假设干( 记录的记录的) 有序子序列，有序子序列，通常称外存中这些记录有序子序列为通常称外存中这些记录有序子序列为 “归并段；归并段；二、外部排序的根本过程二、外部排序的根

39、本过程由相对独立的两个步骤组成： 经过经过“归并，逐渐扩展归并，逐渐扩展 (记录的记录的)有序子序列的长度，直至外存中整个记有序子序列的长度，直至外存中整个记录序列按关键字有序为止。录序列按关键字有序为止。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃例如：假设有一个含例如：假设有一个含10,000个记录的磁盘个记录的磁盘 文件，而当前所用的计算机一次只文件，而当前所用的计算机一次只 能对能对1000个记录进展内部排序，那么个记录进展内部排序，那么 首先利用内部排序的方法得到首先利用内部排序的方法得到10个个 初始归并段，然后进展逐趟归并。初始归并段，然后进展逐趟归并

40、。假设进展2路归并(即两两归并)，那么第一趟由10个归并段得到5个归并段；最后一趟归并得到整个记录的有序序列。最后一趟归并得到整个记录的有序序列。第三趟由第三趟由 3 个归并段得到个归并段得到2个归并段；个归并段；第二趟由第二趟由 5 个归并段得到个归并段得到3个归并段；个归并段；四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃假设“数据块的大小为200，即每一次访问外存可以读/写200个记录。那么对于10,000个记录，处置一遍需访问外存100次(读和写各50次)。分析上述外排过程中访问外存(对外存进展读/写)的次数：四川大学计算机学院，主讲教师：游洪跃四川大学计算机

41、学院，主讲教师：游洪跃由此，对上述例子而言， 1)求得10个初始归并段需访问外存100次； 2)每进展一趟归并需访问外存100次； 3)总计访问外存 100 + 4 100 = 500次。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 外排总的时间还应包括内部排序所需时间和逐趟归并时进展内部归并的时间，显然，除去内部排序的要素外，外部排序的时间取决于逐趟归并所需进展的“趟数。例如，假设对上述例子采用例如，假设对上述例子采用5路归并，路归并，那么只需进展那么只需进展2趟归并，总的访问外存的趟归并，总的访问外存的次数将紧缩到次数将紧缩到 100 + 2 100 = 300

42、 次。次。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 普通情况下，假设待排记录序列含 m 个初始归并段，外排时采用 k路归并，那么归并趟数为 logkm，显然，随之k的增大归并的趟数将减少，因此对外排而言，通常采用多路归并。k 的大小可选，但需综合思索各种要素。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃第第10章章 文件文件四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃有关文件的根本概念有关文件的根本概念四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃一、文件即为记录的集合，和一、文件

43、即为记录的集合，和“查找查找 表的差别在于，表的差别在于，“文件指的是存文件指的是存 储在外存储器中的记录的集合。储在外存储器中的记录的集合。 记录是文件中可以存取的数据的记录是文件中可以存取的数据的 根本单位。根本单位。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二、文件可按其中记录的类型不同而二、文件可按其中记录的类型不同而 分成两类：分成两类：其一为操作系统的文件，文件中的记 录仅是一个字符组。由于操作系 统中的文件仅是一维的延续字符 序列，为了用户存取和加工的方 便，将文件中的信息划分为假设干 组，其中每一组信息称作一个记 录；四川大学计算机学院，主讲教师：

44、游洪跃四川大学计算机学院，主讲教师：游洪跃其二为数据库文件，文件中的记录带 有构造，是数据项的集合。记录 是文件中可以存取的数据根本单 位，数据项是文件中可以运用的 数据最小单位。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃三、记录中能识别不同记录的数据项三、记录中能识别不同记录的数据项 被称为关键字，假设该数据项能唯被称为关键字，假设该数据项能唯 一识别一个记录，那么称为主关键一识别一个记录，那么称为主关键 字，假设能识别多个记录那么称为次字，假设能识别多个记录那么称为次 关键字。关键字。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃四、

45、文件的逻辑构造指的是呈如今用四、文件的逻辑构造指的是呈如今用 户面前的文件中记录之间的逻辑户面前的文件中记录之间的逻辑 关系；文件的物理构造指的是文关系；文件的物理构造指的是文 件中的逻辑记录在存储器中的组件中的逻辑记录在存储器中的组 织方式。织方式。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃顺顺 序序 文文 件件四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃结结 构构 特特 点：点： 记录在文件中的陈列顺序是由记录进入存储介质的次序决议的， 即文件物理构造中记录的陈列顺序和文件的逻辑构造中记录的陈列顺序一致。四川大学计算机学院，主讲教师

46、：游洪跃四川大学计算机学院，主讲教师：游洪跃操作特点：操作特点： 1便于进展顺序存取； 2不便于进展直接存取，为取第i个记录，必需先读出前i-1个记录；四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 3插入新的记录只能加在文件的末尾； 4删除记录时，只作标志； 5更新记录必需生成新的文件。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃索索 引引 文文 件件四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 1索引文件由“主文件和“索引组成； 2索引中的每个记录由“关键字和“指针组成； 3通常，索引文件中的主文件是无序文件

47、，索引是 (按关键字有序)的有序文件； 4“索引是在输入数据建立文件时自动生成。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃二、二、VSAM文件文件VSAM(Vistual Storage Access Method) 文件是利用操作系统中提供的虚拟存储器的功能组织的文件，免除了用户为读/写记录时直接对外存进展的操作，对用户而言，文件只需控制区间和控制区域等逻辑存储单位。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃 . 索引集B+树 顺序集控制区域控制区间数据集数据集1 1文件的构造文件的构造四川大学计算机学院，主讲教师：游洪跃四川大学计

48、算机学院，主讲教师：游洪跃 2. 控制区间是用户进展一次存取的逻辑单位，可看成是一个逻辑磁道。但它的实践大小和物理磁道无关。 VSAM文件初建时，每个控制区间内的记录数缺乏额定数，并且有的控制区间内的记录数为零。 控制区域由假设干控制区间和它们控制区域由假设干控制区间和它们的索引项组成，可看成是一个逻辑柱面。的索引项组成，可看成是一个逻辑柱面。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃顺序集本身是一个单链表，它包含文件的全部索引项，同时，顺序集中的每个结点即为B+树的叶子结点，索引集中的结点即为B+树的非叶结点。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学

49、院，主讲教师：游洪跃文件的操作文件的操作 检索：可进展顺序存取和按关键字存取；检索：可进展顺序存取和按关键字存取； 插入：按关键字大小插入在某个适当的插入：按关键字大小插入在某个适当的控制区间中，当控制区间中的记录数超控制区间中，当控制区间中的记录数超越文件规定的大小时，要越文件规定的大小时，要“分裂控制分裂控制区间，必要时，还需求区间，必要时，还需求“分裂控制区分裂控制区域；域； 删除：必需删除：必需“真实地删除记录，因此真实地删除记录，因此要在控制区间内要在控制区间内“挪动记录。挪动记录。四川大学计算机学院，主讲教师：游洪跃四川大学计算机学院，主讲教师：游洪跃直直 接接 存存 取取 文文 件件四川大学计算机学院，