C增量之数据结构与算法

《C增量之数据结构与算法》由会员分享，可在线阅读，更多相关《C增量之数据结构与算法（89页珍藏版）》请在金锄头文库上搜索。

1、封面封面数据结构与算法数据结构与算法姜学姜学锋锋西北工业大学计算机学院西北工业大学计算机学院参考教材：清华大学数据结构参考教材：清华大学数据结构1.1 概述概述算法算法+数据结构数据结构=程序设计程序设计N.Wirth1.1.1 基本概念和术语基本概念和术语数据（数据（data) 客观事物的符号表示，是所有能输入到计算机中并被计客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。算机程序处理的符号的总称。数据元素数据元素(data element) 数据的基本单位，在计算机程序中通常作为一个整体进数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可

2、由若干个数据项组成。行考虑和处理，一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据项是数据的不可分割的最小单位。数据对象（数据对象（data object)性质相同的数据元素的集合，是数据的一个子集性质相同的数据元素的集合，是数据的一个子集。数据结构（数据结构（data structure)相互之间存在一种或多种特定关系的数据元素的集合相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的关系称为结构，通常有四类基本结构数据元素之间的关系称为结构，通常有四类基本结构.集合集合 线性结构线性结构 树形结构树形结构 图状结构图状结构1.1.1 基本概念和术语基本概念

3、和术语1.1.1 基本概念和术语基本概念和术语数据的逻辑结构数据的逻辑结构 抽象地描述数据元素逻辑关系抽象地描述数据元素逻辑关系。数据的物理结构（存储结构）数据的物理结构（存储结构） 数据结构在计算机中的表示数据结构在计算机中的表示。 10 20 30102030 顺序映像 用相对位置表示数据元素间的逻辑关系 非顺序映像用指针表示数据元素间的逻辑关系D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) D= 1 , 2 , 3 R= , , , 例例 1: 1: 英文英文2626个字母表的数据结构是一个线形个字母表的数据结

4、构是一个线形表，可表示为表，可表示为: : B=D,R B=D,R D= a , b, c, D= a , b, c, ，x x ,y ,z,y ,z R=(a,b),(b,c), R=(a,b),(b,c),，(y,z)(y,z) 此例数据元素是简单项。此例数据元素是简单项。1. 数据的逻辑结构数据的逻辑结构 2. 数据的存储结构数据的存储结构 3. 数据的运算：检索、排序、插入、删除、修改等。数据的运算：检索、排序、插入、删除、修改等。 A . 线性结构线性结构 B . 非线性结构非线性结构A . 顺序存储顺序存储 B . 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形

5、结构数据结构的三个方面数据结构的三个方面反映数据元素反映数据元素之间的逻辑关之间的逻辑关系系数据元素在计算机数据元素在计算机内部的组织方式内部的组织方式1.1.2 算法描述算法描述算法（算法（algorithm) 对特定问题求解步骤的一种描述，它是指令的有限序列对特定问题求解步骤的一种描述，它是指令的有限序列。算法的特性算法的特性 有穷性、确定性、可行性、输入、输出。有穷性、确定性、可行性、输入、输出。算法设计的要求算法设计的要求 正确性、正确性、 可读性、可读性、 健壮性、健壮性、 效率效率。1.1.2 算法描述算法描述算法的时间复杂度算法的时间复杂度:以算法中基本操作重复执行的次数作为算法

6、的时间度量。以算法中基本操作重复执行的次数作为算法的时间度量。例例2: (a) x=x+1;O(1) (b) for (i=0;in;i+) x=x+1;O(n) (c) for (i=1;in;i+) for (j=1;jnextNULLhead-nextNULL，则为非空单链表；则为非空单链表； 若若 head-nexthead-nextNULLNULL，则为空单链表。则为空单链表。 1.2.2 线性表的链式存储结构线性表的链式存储结构一、单链表一、单链表带表头结点的带表头结点的循环循环单链表的一般形式单链表的一般形式 若若 head-nextheadhead-nexthead，则为非空则

7、为非空循环循环单链表；单链表； 若若 head-nexthead-nextheadhead，则为空则为空循环循环单链表。单链表。 二、双向链表二、双向链表双向链表的结点结构双向链表的结点结构 结点类型说明结点类型说明: struct nodedou element data； struct nodedou *llink; struct nodedou *rlink; 二、双向链表二、双向链表带表头结点的双向链表带表头结点的双向链表 (1) (1) 非空表非空表( (首结点的左指针为空，尾结点的右指针为空首结点的左指针为空，尾结点的右指针为空) ) h h a1 . an a1 . an 头指针

8、头指针 表头结点表头结点 首结点首结点 尾结点尾结点 (2) (2) 空表空表 h h 头指针头指针 表头结点表头结点1.2.3 数组及其顺序存储数组及其顺序存储一、组和一、组和数组的运算数组的运算对数组的运算对数组的运算: : (1)(1)给定一个有定义的下标组，访问与其对应的数组元素。给定一个有定义的下标组，访问与其对应的数组元素。 (2)(2)给定一个有定义的下标组，存取或修改与其对应的数组元素。给定一个有定义的下标组，存取或修改与其对应的数组元素。 1.2.3 数组及其顺序存储数组及其顺序存储一、组和一、组和数组的运算数组的运算 例例 二维数组二维数组: : 11 11 12 12 2

9、1 21 22 22 31 31 32 32 41 41 42 42 (1) (1) 以行序为主序的顺序存储方式以行序为主序的顺序存储方式: : 111112122121222231313232414142 42 序号序号: 1 2 3 4 5 6 7 8 : 1 2 3 4 5 6 7 8 (2) (2) 以列序为主序的顺序存储方式以列序为主序的顺序存储方式: : 111121213131414112122222323242 42 序号序号: 1 2 3 4 5 6 7 8 : 1 2 3 4 5 6 7 8 1.3 栈和队列栈和队列1.3.1 栈栈定义和术语定义和术语(1)(1)栈栈( (

10、stack): stack): 只只允允许许在在表表的的一一端端插插入入和删除元素的线性表。和删除元素的线性表。 (2)(2)栈栈顶顶( (top): top): 线线性性表表中中允允许许进进行行插插入入和删除的一端。和删除的一端。 (3)(3)栈栈底底( (bottom): bottom): 线线性性表表中中不不允允许许进进行行插入和删除的一端。插入和删除的一端。 (4)(4)栈顶元素栈顶元素: : 位于栈顶的元素。位于栈顶的元素。 (5)(5)栈底元素栈底元素: : 位于栈底的元素。位于栈底的元素。 (6)(6)空栈空栈: : 不含元素的栈。不含元素的栈。 (7)(7)进进栈栈( ( pu

11、sh, push, 下下推推 , , 压压入入 ): ): 插插入入一个新元素到栈中。一个新元素到栈中。 (8)(8)退栈退栈( ( POP, POP, 弹出弹出 ): ): 删除栈顶元素。删除栈顶元素。 (9)(9)栈中元素的进出原则栈中元素的进出原则: : 后进先出后进先出( ( Last In Last In First Out)First Out)。 (10)(10)栈的别名栈的别名: “: “后进先出表后进先出表”或或“LIFOLIFO”表表 退栈退栈进栈进栈 4 4 top top 3 3 栈顶元素栈顶元素 2 2 bottom bottom 1 1 栈底元素栈底元素 栈的图示栈的

12、图示 1.3.1 栈栈一、栈的定义一、栈的定义栈的基本操作栈的基本操作(1) (1) init(s) init(s) 初始化，将栈设置为空栈初始化，将栈设置为空栈 (2) (2) empty(s) empty(s) 判断栈是否为空栈判断栈是否为空栈 (3) (3) push(s,x) push(s,x) 将元素压入栈中将元素压入栈中 (4) (4) pop(s) pop(s) 弹出栈的顶元素弹出栈的顶元素(5) (5) gettopgettop(s) (s) 读取栈顶元素读取栈顶元素(6) (6) clear(s) clear(s) 栈置空操作栈置空操作(7) (7) length(s) le

13、ngth(s) 求当前栈中元素的个数求当前栈中元素的个数 一、栈的定义一、栈的定义例例 由输入由输入( (A,B,C), A,B,C), 得输出得输出( ( C,B,A )C,B,A )的操作的操作 A,B,C C,B,A A,B,C C,B,A next=p; tail-next=p; tail=p;tail=p;二、链队列二、链队列 headhead A A tail tail headA headA 首结点首结点 B B tailC tailC 尾结点尾结点 出队算法出队算法if (head=NULL)if (head=NULL) /* /* 空队列空队列 */ */ else else

14、 p=head; p=head; head=head-next; head=head-next; if (head=NULL) if (head=NULL) tail=NULL; tail=NULL; 三、循环队列三、循环队列 如果采用数组如果采用数组q6,q6,设两个指针设两个指针 headhead指向队首指向队首 tailtail指向队尾指向队尾空队列空队列 head=tailhead=tail - - - - 0 1 2 3 4 5 0 1 2 3 4 5 H T ( H T (带头结点链表？）带头结点链表？） 插入插入 A,B,C,D,E A,B,C,D,E 之后之后 - - ABCD

15、EABCDE - - 0 1 2 3 4 5 0 1 2 3 4 5 H H T T删除删除 A,B,C A,B,C 之后之后 - - DE DE - - 0 1 2 3 4 5 0 1 2 3 4 5 H T H T 插入插入F F发生假发生假“溢出溢出”. . - - DE F DE F - - 0 1 2 3 4 5 0 1 2 3 4 5 H T H T三、循环队列三、循环队列 循环队列循环队列插入插入F tail=(tail+1)%6 F tail=(tail+1)%6 - - F DE F DE - - 0 1 2 3 4 5 0 1 2 3 4 5 T H T H插入插入G,H,

16、G,H,队列满队列满 ( (tail+1)%6=head tail+1)%6=head - - FGH DE FGH DE - - 0 1 2 3 4 5 0 1 2 3 4 5 T H T H tail 0 tail 0 5 F 1 5 F 1 E E 4 D 2 4 D 2 3 head 3 head 0 5 F 1 E G 4 D H 2 tail 3 head1.4 1.4 树树1.4.1 1.4.1 树及存储结构树及存储结构一、树的基本概念一、树的基本概念定义定义 树树是是一一个个或或多多个个结结点点的的有有穷穷集集合合T T，其其中中有有且且仅仅有有一一个个指指定定的的称称为为树树

17、根根( (root)root)的的结结点点，除除树树根根之之外外的的其其余余结结点点被被分分为为 m m ( ( m m 0 0 ) )个个互互不不相相交交的的集集合合T1T1，T2T2，.，TmTm， 每每一一个个Ti(i Ti(i = = 1 1，2 2，.，m)m)又又都都是是树树，并并且称为根的子树。且称为根的子树。 例例1. 1. 一个结点的树一个结点的树 T T A A 1.4.1 1.4.1 树及存储结构树及存储结构一、树的基本概念一、树的基本概念例例2. 12 2. 12 个结点的树个结点的树 1 1 T T A, B, C, D, E, F, G, H, I, J, K, L

18、 A, B, C, D, E, F, G, H, I, J, K, L 2 T1 2 T1 B, E, F, J B, E, F, J . . 第第1 1层层 3 3 T11T11 E E 4 T12 4 T12 F, J F, J 5 T121 5 T121 J J . . 第第2 2层层 6 6 T2T2 C C 7 T3 7 T3 D, G, H, I, K, L D, G, H, I, K, L 8 T31 8 T31 G, K, L G, K, L . . 第第3 3层层 9 9 T311T311 K K 10 T312 10 T312 L L 11 T32 11 T32 H H .

19、 . 第第4 4层层 12 12 T33T33 I I 一棵树的图示一棵树的图示 1.4.1 1.4.1 树及存储结构树及存储结构一、树的基本概念一、树的基本概念 基本术语基本术语 (1)(1)结点的度结点的度： 结点结点 X X 的子树数称为结点的子树数称为结点 X X 的度的度( ( degree ) degree ) (2)(2)树的度树的度： 树树 T T 中各结点的度的最大值称为树中各结点的度的最大值称为树 T T 的度。度为的度。度为 d d 的树称为的树称为 d d 度树度树 (3)(3)叶子叶子： 树中度为树中度为 0 0 的结点称为叶子的结点称为叶子( (leaf)leaf)

20、或终端结点或终端结点(4)(4)分枝结点分枝结点( ( 非终端结点、非叶子非终端结点、非叶子 ) )： 树中度不为树中度不为 0 0 的结点的结点 (5)(5)双亲和孩子双亲和孩子： 若树中结点若树中结点 P P 的一棵子树的根是结点的一棵子树的根是结点 C C，则称结点则称结点 P P是结点是结点 C C 的的双亲或父母双亲或父母( ( parent )parent )；反之，称结点反之，称结点 C C是结点是结点 P P 的孩子的孩子( ( child )child )(6)(6)结点的层结点的层： 规定树的根结点的层规定树的根结点的层( ( level )level )为为 1 1，其余

21、任一结点的层等于它的双，其余任一结点的层等于它的双亲的层加亲的层加1 1(7)(7)树的深度树的深度： 树树 T T 中各结点的层的最大值称为树中各结点的层的最大值称为树 T T 的深度或高度的深度或高度 (8)(8)兄弟和堂兄弟兄弟和堂兄弟： 同一个双亲的孩子之间互称为兄弟同一个双亲的孩子之间互称为兄弟( ( sibling )sibling )，其双亲在同一其双亲在同一层的结点互为堂兄弟层的结点互为堂兄弟 (9)(9)祖先和子孙祖先和子孙： 一个结点的祖先是指从树的根到该结点所经分枝上的所有结点，一一个结点的祖先是指从树的根到该结点所经分枝上的所有结点，一个结点的子树的所有结点称为该结点的

22、子孙个结点的子树的所有结点称为该结点的子孙(10)(10)有序树和无序树有序树和无序树： 如果树如果树 T T 中任一结点的各棵子树规定从左至右是有次序的，中任一结点的各棵子树规定从左至右是有次序的，即不能互换位置，则称树即不能互换位置，则称树 T T 为有序树；否则树为有序树；否则树 T T 为无序树为无序树(11)(11)森林森林： n(n=0)n(n=0)棵互不相交的树的集合称为森林棵互不相交的树的集合称为森林1.4.1 1.4.1 树及存储结构树及存储结构一、树的基本概念一、树的基本概念 例例3.3.有序树和无序树有序树和无序树 两棵不同的有序树两棵不同的有序树 两棵相同的无序树两棵相

23、同的无序树 例例4. 4. 森林森林 F F T1, T2, T3 T1, T2, T3 T1 T2 T3T1 T2 T31.4.2 二叉树及其存储结构二叉树及其存储结构一、二叉树的基本概念一、二叉树的基本概念二叉树的递归定义二叉树的递归定义 二二叉叉树树是是有有限限个个结结点点的的集集合合，它它或或者者为为空空集集，或或者者是是由由一一个个根根结结点点和和两两棵棵互互不不相相交交的的且且分分别别称称为根的左子树和右子树的二叉树所组成。若二叉树为空集，则称之为空二叉树。为根的左子树和右子树的二叉树所组成。若二叉树为空集，则称之为空二叉树。 二叉树的二叉树的 5 5 种基本形态种基本形态 (1)

24、 (2) (3) (4) (5) (1) (2) (3) (4) (5) 空二叉树空二叉树 只有根结点只有根结点 有根结点有根结点 有根结点有根结点 有根结点有根结点 左、右子树左、右子树 左子树非空左子树非空 左子树为空左子树为空 左子树非空左子树非空 为空二叉树为空二叉树 右子树为空右子树为空 右子树非空右子树非空 右子树非空右子树非空 一、二叉树的基本概念一、二叉树的基本概念二叉树和二叉树和 2 度树的区别度树的区别 (1)二叉树的度小于等于二叉树的度小于等于 2；而；而 2 度树的度等于度树的度等于 2。 (2)二叉树的左子树和右子树是有序的；而二叉树的左子树和右子树是有序的；而 2

25、度树可以不规定各子树之间的次序，度树可以不规定各子树之间的次序， 即可以是有序树，也可以是无序树。即可以是有序树，也可以是无序树。 例例. T1 T2 T4 T5 T1、T2是两棵不同的二叉树，但不是是两棵不同的二叉树，但不是 2 度树。度树。 T4、T5是两棵不同的二叉树；是相同的无序是两棵不同的二叉树；是相同的无序 2 度树。度树。一、二叉树的基本概念一、二叉树的基本概念具有具有 3 个结点的不同形态的二叉树个结点的不同形态的二叉树 T1 T2 T3 T4 T5 一、二叉树的基本概念一、二叉树的基本概念性质性质 1 1： 在任意二叉树的第层上，最多有在任意二叉树的第层上，最多有i-1i-1

26、个结点个结点( (1)1)。 例例. . . . 第第 1 1 层层 1-11-1 1 1 . . 第第 2 2 层层 2-12-1 2 2 . . 第第 3 3 层层 3-13-1 4 4 . . 第第 4 4 层层 4-14-1 8 8 二、二叉树的性质二、二叉树的性质性质性质 2 2： 深度为深度为 k k 的二叉树最多有的二叉树最多有 2 2k k 1 ( k 1 ) 1 ( k 1 )个结点。个结点。 由性质由性质 1 1 知，深度为的二叉树的结点总数最多为：知，深度为的二叉树的结点总数最多为： k k ik k i1 1 ( (第层上结点的最多数目）第层上结点的最多数目） 2 2

27、i=1 i=1i=1 i=1 例例. . T4 T4 T1 T2 T3 T1 T2 T3 2 21 11 11 21 22 21 13 23 23 31 17 27 24 41 115 15 二、二叉树的性质二、二叉树的性质性质性质3 3： 对于任一非空二叉树，如果它的叶子数目为对于任一非空二叉树，如果它的叶子数目为0 0，度为，度为 2 2 的结点数目为的结点数目为2 2，则有：，则有： 0 02 2 (2 (2n n2 2+1=n+1=n0 0+n+n2 2) ) 例例 T1 T2 T3 T4 T1 T2 T3 T4 0 01 1 0 02 2 0 04 4 0 05 5 2 20 0 2

28、 21 1 2 23 3 2 24 4 三、特殊二叉三、特殊二叉树树特殊二叉树特殊二叉树 满二叉树、完全二叉树、顺序二叉树满二叉树、完全二叉树、顺序二叉树(1) (1) 满二叉树满二叉树: : 深度为深度为 k k 的具有的具有 2 2k k 1 1 个结点的二叉树称为满二叉树个结点的二叉树称为满二叉树 ( ( k 1 ). k 1 ). 例：例： T1 T2 T3 T4 T1 T2 T3 T4 k k1 k1 k2 k2 k3 k3 k4 4 2 21 1 1 11 21 22 2 1 13 23 23 3 1 17 27 24 4 1 115 15 三、特殊二叉树三、特殊二叉树 顺序编号的

29、满二叉树顺序编号的满二叉树: : 从根结点开始，从上至下；同层的结点从左至右；从根结点开始，从上至下；同层的结点从左至右；n n 个结点的满二叉树，个结点的满二叉树， 依次用依次用 1 1，2 2，n n 顺序编号。顺序编号。 例例. .顺序编号的满二叉树顺序编号的满二叉树 T1 T2 T3 T1 T2 T3 n n1 n1 n3 n3 n7 7 满二叉树的结点个数与树的深度之间的关系：具有满二叉树的结点个数与树的深度之间的关系：具有 n n 个结点的满二叉树的深度为个结点的满二叉树的深度为 loglog2 2（n n1 1）。）。 依定义依定义, ,一棵深度为一棵深度为 k k 的满二叉树有

30、的满二叉树有 2 2k k 1 1 个结点），有：个结点），有： 2 2k k 1 1 n n 三、特殊二叉树三、特殊二叉树(2) 完全二叉树完全二叉树 若二叉树的任一结点的度为若二叉树的任一结点的度为 0 或者为或者为 2，则称该二叉树为完全二叉树。，则称该二叉树为完全二叉树。 例例.完全二叉树完全二叉树 T1 T2 T3 T4 一棵满二叉树同时又是一棵完全二叉树；反之，一棵完全二叉树不一定是一棵满二叉树。当且一棵满二叉树同时又是一棵完全二叉树；反之，一棵完全二叉树不一定是一棵满二叉树。当且仅当一棵深度为仅当一棵深度为 k 的完全二叉树具有的完全二叉树具有 2k 1 个结点时，称该完全二叉树

31、为满二叉树。个结点时，称该完全二叉树为满二叉树。1.4.3 遍历二叉树遍历二叉树遍历二叉树遍历二叉树( ( traversing binary tree )traversing binary tree ) 按照某种规则去访问二叉树的每个结点，而且每个结点仅被访问一次。按照某种规则去访问二叉树的每个结点，而且每个结点仅被访问一次。 设设 N N 访问根结点访问根结点 L L 遍历根结点的左子树遍历根结点的左子树 R R 遍历根结点的右子树遍历根结点的右子树 分为分为 6 6 种不同的遍历规则：种不同的遍历规则： NLR NLR 前序前序 ( ( preorder ) preorder ) 遍历，

32、或先根遍历。遍历，或先根遍历。 LNR LNR 中序中序 ( ( inorderinorder ) ) 遍历，或中根遍历。遍历，或中根遍历。 LRN LRN 后序后序 ( ( postorderpostorder ) ) 遍历，或后根遍历。遍历，或后根遍历。 NRL NRL 逆前序遍历，或逆先根遍历。逆前序遍历，或逆先根遍历。 RNL RNL 逆中序遍历，或逆中根遍历。逆中序遍历，或逆中根遍历。 RLN RLN 逆后序遍历，或逆后根遍历。逆后序遍历，或逆后根遍历。 注意：以某种规则遍历一棵二叉树，是以同一规则去遍历根的左、右子树的，注意：以某种规则遍历一棵二叉树，是以同一规则去遍历根的左、右子

33、树的， 是一个递归过程。是一个递归过程。 一、前序遍历一、前序遍历前序遍历二叉树递归定义：前序遍历二叉树递归定义： 若二叉树为空，则遍历结束；若二叉树为空，则遍历结束； 否则，执行下列步骤：否则，执行下列步骤： (1) (1) 访问根结点；访问根结点； (2) (2) 遍历根的左子树；遍历根的左子树； (3) (3) 遍历根的右子树。遍历根的右子树。 例例1. 1. 前序遍历过程：前序遍历过程： 前序序列：前序序列： 二、中序遍历二、中序遍历中序遍历二叉树递归定义：中序遍历二叉树递归定义： 若二叉树为空，则遍历结束；若二叉树为空，则遍历结束； 否则，执行下列步骤：否则，执行下列步骤： (1)

34、(1) 遍历根的左子树；遍历根的左子树； (2) (2) 访问根结点；访问根结点； (3) (3) 遍历根的右子树。遍历根的右子树。 例例1. 1. 中序遍历过程：中序遍历过程： 中序序列：中序序列： H B D C A G E F H B D C A G E F 三、后序遍历三、后序遍历后序遍历二叉树递归定义：后序遍历二叉树递归定义： 若二叉树为空，则遍历结束；若二叉树为空，则遍历结束； 否则，执行下列步骤：否则，执行下列步骤： (1) (1) 遍历根的左子树；遍历根的左子树； (2) (2) 遍历根的右子树。遍历根的右子树。 (3) (3) 访问根结点；访问根结点； 例例1. 1. 后序遍

35、历过程：后序遍历过程： 后序序列：后序序列： H D C B G F E A H D C B G F E A 三、后序遍历三、后序遍历根据遍历的结果构造原来的二叉树：根据遍历的结果构造原来的二叉树： 例：已知对某二叉树的例：已知对某二叉树的 前序遍历结果前序遍历结果 中序遍历结果中序遍历结果 H B D C A G E F H B D C A G E F 求对该二叉树的后序遍历结果求对该二叉树的后序遍历结果. .1.5 查找查找1. 1. 目标目标 确定一个好的查找算法，以提高程序的执行速度。确定一个好的查找算法，以提高程序的执行速度。 2. 2. 关键字关键字( ( key ) key )

36、标识记录的数据项称为记录的关键字标识记录的数据项称为记录的关键字( ( key )key )。 例例. . 电话号码本电话号码本 序号序号 姓姓 名名 住住 址址 电电 话话 号号 码码 1 1 张大海张大海 旺园旺园A101A101号号 8823 88237211 7211 R1 R1 2 2 吴林林吴林林 旺园旺园A112A112号号 8823 88237218 7218 R2 R2 3 3 刘晓平刘晓平 17 17舍舍-224-224号号 8849 88491234 1234 R3 R3 4 4 王王 伟伟 新区新区A A-299-299号号 8831 88311221 1221 R4

37、R4 5 5 李李 娟娟 21 21舍舍-414-414号号 8849 88492234 2234 R5 R5 数据项数据项1 1 数据项数据项2 2 数据项数据项3 3 ( ( 关键字关键字 key ) key ) 1.5 查找查找 3. 3. 查找查找 假定由假定由 n n 个记录组成一个表个记录组成一个表 ( ( 文件文件 ) ) F F （ R R1 1，R R2 2，R Rn n ） 记录记录 Ri Ri 的关键字是的关键字是 keykeyi i( ( 1 1，2 2，n )n ) k k 是指定的一个关键字，在是指定的一个关键字，在 F F 中确定一个关键字中确定一个关键字 key

38、keyi i k k 的记录的记录 R Ri i，这个过这个过程称为查找。程称为查找。 如果确定了关键字为如果确定了关键字为 K K 的记录的记录 R Ri i，或者说在文件或者说在文件 F F 中找到了要查找的记录，中找到了要查找的记录， 则称此次查找是成功的则称此次查找是成功的( ( success )success )。 如果没有找到关键字为如果没有找到关键字为 K K 的记录，则称此次查找失败的记录，则称此次查找失败( ( fail )fail )。 1.5 查找查找4. 4. 顺序表的基本查找方法顺序表的基本查找方法 假定记录按逻辑次序顺序存储在一个连续存储区中，个记录用数组假定记录

39、按逻辑次序顺序存储在一个连续存储区中，个记录用数组1.1. .n n 表表示，用示，用C C语言说明如下：语言说明如下： struct struct record record keytype keytype key;key; othertype otherdataothertype otherdata; ; struct recored struct recored rn+1; rn+1; (1) (1) 顺序查找法顺序查找法 不要求表中记录按关键字的大小排序不要求表中记录按关键字的大小排序(2) (2) 折半查找法折半查找法 仅适用于记录按关键字的递增或递减次序排列的顺序表仅适用于记录按关

40、键字的递增或递减次序排列的顺序表1.5.1 1.5.1 顺序查找顺序查找法法1 1 问题问题 假假定定 n n 个个记记录录已已存存入入一一维维数数组组1.1.nn，其其中中第第(1(1inin）个个记记录录 ii的的关关键键字字为为 i.keyi.key，查查找找中关键字为中关键字为 的记录。的记录。 2 2 算法基本思想算法基本思想 将将依依次次与与 n.keyn.key， n-1.keyn-1.key，.，11.key key 进进行行比比较较，如如果果找找到到一一个个记记录录 ii，有有 i.keyi.keyk k ( ( 1in 1in ) )，则则查查找找成成功功，停停止止比比较较

41、，返返回回记记录录的的下下标；否则，查找失败，返回标；否则，查找失败，返回 0 0。 r1r2r3. r1r2r3. rnrn 0 1 2 3 n 0 1 2 3 n i i 1.5.1 1.5.1 顺序查找法顺序查找法3 3 改进的顺序查找算法改进的顺序查找算法 为避免每次循环之前判定条件为避免每次循环之前判定条件是否成立，可以利用未存是否成立，可以利用未存入记录数据的入记录数据的00，将它看作一个监视哨。首先将指定的关，将它看作一个监视哨。首先将指定的关键字送入键字送入0.0.key key 中，再按上述顺序查找算法进行查找。中，再按上述顺序查找算法进行查找。 监视哨监视哨 1.1.n n

42、 kr1r2r3 kr1r2r3 rnrn 0 1 2 3 0 1 2 3 n n i i 4 4 查找算法性能评价：查找算法性能评价： 对对 n n 个记录进行顺序查找，若查找成功，则所需比较关键字个记录进行顺序查找，若查找成功，则所需比较关键字的次数最少为的次数最少为 1 1，最多为，最多为 n n。假定每个记录的查找概率相同，假定每个记录的查找概率相同，那么，平均比较次数大约为那么，平均比较次数大约为 ( (n n1) / 2 1) / 2 ；若查找失败，则所若查找失败，则所需比较次数为需比较次数为 n n1 1。 1.5.2 1.5.2 折半查找法折半查找法1. 1. 折半查找的条件折

43、半查找的条件 (1) (1) 被查的文件采用顺序存储结构；被查的文件采用顺序存储结构； (2) (2) 记录按关键字大小次序排列。记录按关键字大小次序排列。 2. 2. 折半查找的步骤折半查找的步骤 (0) (0) 置置 lowlow1 1， high highn n - - 112.2. n n - - low low highhigh (1) (1) 计算计算 mid mid (low + high)/2(low + high)/2，确定一个中间位置上的记录确定一个中间位置上的记录 midmid - - low . low . mid .mid . high high - - low mi

44、d low mid high high 1.5.2 1.5.2 折半查找法折半查找法 (2) (2) k k 与中间记录的关键字与中间记录的关键字 mid.key mid.key 比较大小，有下面三种情况之一：比较大小，有下面三种情况之一： 若若 k k mid.keymid.key，那么，待查的记录必定在前半区那么，待查的记录必定在前半区 low . midlow . mid1 1 中中( (当存在关当存在关键字值为键字值为 k k 的记录时的记录时) )，此时再对前半区进行折半查找，此时再对前半区进行折半查找， 即令即令 high high mid - 1mid - 1， 转转(1)(1)

45、； low low lowlow1.1. midmid1 1 low low high high 若若 k k mid.keymid.key，那么，那么， mid mid 就是所要查找的记录，结束查找；就是所要查找的记录，结束查找； 若若 k k mid.keymid.key，那么，待查的记录必定在后半区那么，待查的记录必定在后半区 midmid1 .1 . hig hig 中中 ( ( 当存在当存在关键字值为关键字值为 k k 的记录时的记录时 ) )，此时再对后半区进行折半查找，即令，此时再对后半区进行折半查找，即令 low low mid + 1 mid + 1， 转转(1)(1)； m

46、id+1 mid+1 midmid2.2. high high low low highhigh 当当 low high low high 时重复时重复(1)(1)、(2)(2)；直到；直到 low low high high 时，表明表中无要查找的记录，结束查时，表明表中无要查找的记录，结束查找。找。1.5.2 1.5.2 折半查找法折半查找法例例. .查找关键字查找关键字 k k65 65 的记录的记录 1) 1)置置lowlow1 1，highhigh8 8 318475465839497 318475465839497 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 |

47、 | | | | | low mid low mid high high 2)low=high, 2)low54,6554, 故应查故应查后半区。后半区。lowlowmidmid1 15.5. 318475465839497 318475465839497 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 | | | | | | low mid high low mid high 3)low=high, 3)low=high,计算计算mid=6mid=6，比较比较k k与与 rmid.keyrmid.key的大小，因为的大小，因为6583, 6583, 故应查故应查前半区。前半区

48、。highhighmid-1mid-15 5 318475465839497 318475465839497 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 /| /| / / | | low mid high low mid high 4)low=high, 4)low=high,计算计算mid=5,mid=5,比较比较k k与与 rmid.keyrmid.key的大小，因为的大小，因为65=65, 65=65, 查找成查找成功，结果为第功，结果为第5个记录个记录。共计比较。共计比较3 3次。次。例例. .查找关键字查找关键字 k k66 66 的记录的记录 4) 4)low

49、=high,low65, 6665, 故应查故应查后半区。后半区。low=mid+1low=mid+16 6 5)lowhigh 5)lowhigh，表中无要查找的记录，结束表中无要查找的记录，结束查找查找1.6 排序排序1.6.1 什么是排序什么是排序1. 1. 什么是排序什么是排序 将任一文件中的记录，通过某种方法整理成按关键字递增将任一文件中的记录，通过某种方法整理成按关键字递增( (或递减或递减) )次序排列次序排列 的处理过程。的处理过程。 假如给定假如给定 n n 个记录的文件为个记录的文件为 ( ( R R1 1，R R2 2，R Rn n ) ) 对应的关键字为对应的关键字为

50、( ( K K1 1，K K2 2，K Kn n ) ) 则排序是确定如下一个排列则排序是确定如下一个排列 p p1 1，p p2 2，p pn n 使得使得 KpKp1 1 Kp Kp2 2 KpKpn n 从而得到一个有序文件从而得到一个有序文件 ( ( RpRp1 1，RpRp2 2，RpRpn n ) )1.6 排序排序1.6.1 什么是排序什么是排序2. 2. 什么是排序的稳定性什么是排序的稳定性 假设在待排序的文件中，存在两个具有相同关键字的记录假设在待排序的文件中，存在两个具有相同关键字的记录 R(i)R(i)与与R(j)R(j)， 其中其中 R(i) R(i) 位于位于 R(j

51、) R(j) 之前。在用某种排序法排序之后，之前。在用某种排序法排序之后，R(i) R(i) 仍位于仍位于 R(j)R(j) 之前，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。之前，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。 例如，给定数列例如，给定数列 ( 10 ( 10，2525，2222，4242，2525，3030，18 ) 18 ) 排序后，若为排序后，若为 ( 10 ( 10，1818，2222，2525，2525，3030，42 ) 42 ) 则称此过程是稳定的排序；则称此过程是稳定的排序； 排序后，若为排序后，若为 ( 10 ( 10，1818，2

52、222，2525，2525，3030，42 ) 42 ) 则称此过程是不稳定的排序。则称此过程是不稳定的排序。1.6 排序排序1.6.1 什么是排序什么是排序3. 3. 排序方法排序方法 (1) (1) 内部排序内部排序 若被排序的文件较小，则可以将文件记录全部放在内存中，适用于这种情况若被排序的文件较小，则可以将文件记录全部放在内存中，适用于这种情况 的排序方法称为内部排序法。的排序方法称为内部排序法。 (2) (2) 外部排序外部排序 若被排序的文件很大，以致于不能同时将文件记录全部放在内存中，而需要若被排序的文件很大，以致于不能同时将文件记录全部放在内存中，而需要 将部分或全部记录存放在

53、外存储器将部分或全部记录存放在外存储器( (磁盘、磁带等磁盘、磁带等) )中，适用于这种情况的排中，适用于这种情况的排 序方法称为外部排序法。序方法称为外部排序法。 4. 4. 评价一个排序算法好坏的标准评价一个排序算法好坏的标准 (1) (1) 对对 n n 个记录的文件排序所需比较关键字的次数；个记录的文件排序所需比较关键字的次数； (2) (2) 对对 n n 个记录的文件排序所需移动记录的次数；个记录的文件排序所需移动记录的次数； (3) (3) 排序过程中所需的辅助存储空间的大小。排序过程中所需的辅助存储空间的大小。 在下述讨论中约定：文件的存储结构采用顺序结构，即使用一维数组在下述

54、讨论中约定：文件的存储结构采用顺序结构，即使用一维数组 R0.n R0.n 中中的的 R1.nR1.n表示表示 n n 个记录的文件。个记录的文件。1.6.2 简单排序简单排序一、冒泡排序一、冒泡排序 算法基本思想算法基本思想 设待排序的文件为设待排序的文件为( (R1R1，R2R2，RnRn),),关键字为关键字为( (R1.keyR1.key，R2.keyR2.key，RnRn.key).key) 第第 1 1 遍：遍： 从从 R(1) R(1) 开始，依次比较两个相邻记录的关键字开始，依次比较两个相邻记录的关键字 R(i).key R(i).key 和和R(iR(i1).key 1).k

55、ey ( (1 1，2 2，n n1)1)。若若 R(i).keyR(i).keyR(iR(i1).key1).key，则交换相应记录则交换相应记录 R(i) R(i) 和和 R(iR(i1)1)的存储位置；否则，不进行交换。的存储位置；否则，不进行交换。 第第1 1遍之后，遍之后，n n 个记录中关键字最大的记录移到了第个记录中关键字最大的记录移到了第 n n 个位置上。个位置上。 第第 2 2 遍：遍： 从从 R(1) R(1) 开始，依次比较两个相邻记录的关键字开始，依次比较两个相邻记录的关键字 R(i).key R(i).key 和和R(iR(i1).key 1).key ( (1 1

56、，2 2，n n2)2)。若若 R(i).keyR(i).keyR(iR(i1).key1).key，则交换相应记录则交换相应记录 R(i) R(i) 和和 R(iR(i1)1)的存储位置；否则，不进行交换。的存储位置；否则，不进行交换。 第第2 2遍之后，前遍之后，前 n n1 1 个记录中关键字最大的记录移到了第个记录中关键字最大的记录移到了第 n n1 1个位置上个位置上 继续进行下去，直到第继续进行下去，直到第 n n1 1 遍之后，或者不需要再交换记录为止。遍之后，或者不需要再交换记录为止。1.6.2 简单排序简单排序一、冒泡排序一、冒泡排序例：例： 第第 1 1 遍遍 第第 2 2

57、 遍遍 第第 3 3 遍遍 第第 4 4 遍遍 k1 k1 4343 21 21 21 21 21 21 21 21 21 21 21 15 15 15 15 15 15 21 21 21 21 21 21 21 21 21 21 21 15 15 15 15 15 15 k2 21 k2 21 43 43 43 43 43 43 4343 43 43 43 43 43 43 15 15 15 15 15 15 15 15 21 21 21 21 21 21 21 21 21 21 21 21 k3 89 89 89 15 15 15 15 15 k3 89 89 89 15 15 15 15

58、 15 43 43 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 k4 15 15 15 89 28 28 28 28 28 k4 15 15 15 89 28 28 28 28 28 43 43 43 43 43 43 4343 43 43 43 43 43 43 k5 28 28 28 28 89 k5 28 28 28 28 89 43 43 43 43 4343 43 43 43 43 43 43 43 43 4343 k6 k6 43 43 43 43 4343 43 43 43 43 89 89 89 89 89 89

59、89 89 比较次数为比较次数为 5 54 43 32 214 14 1.6.2 简单排序简单排序一、冒泡排序一、冒泡排序算法分析算法分析 (1) (1) 最好情况最好情况: : 待排序的文件已是有序文件，只需要进行待排序的文件已是有序文件，只需要进行 1 1 遍排序，遍排序，共计比较关键字的次数为共计比较关键字的次数为 minminn n1 1 不交换记录。不交换记录。 (2) (2) 最坏情况最坏情况: : 要经过要经过 n n1 1 遍排序，所需总的比较关键字的次数遍排序，所需总的比较关键字的次数为为 maxmax(n-1)+(n-2)+(n-1)+(n-2)+1 +1 n(n-1)/2

60、 n(n-1)/2 交换记录的次数最多为交换记录的次数最多为n(n-1)/2 n(n-1)/2 移动记录次数最多为移动记录次数最多为3 3n(n-1)/2 n(n-1)/2 只需要少量中间变量作为辅助空间，算法是稳定的只需要少量中间变量作为辅助空间，算法是稳定的二、选择排序二、选择排序算法基本思想算法基本思想 设待排序的文件为设待排序的文件为( (R1R1，R2R2，RnRn),),关键字为关键字为( (R1.keyR1.key，R2.keyR2.key，RnRn.key).key) 第第 1 1 遍：遍： 在在 n n 个记录中个记录中, , 选出具有最小关键字的记录，需要进行选出具有最小关

61、键字的记录，需要进行 n n1 1 次比较。次比较。 第第 2 2 遍：遍： 在余下的在余下的 n n1 1 个记录中，选出最小关键字的记录，需要进行个记录中，选出最小关键字的记录，需要进行 n n2 2 次比较。次比较。 . . . . . . 第第 n n1 1 遍：遍： 在最后的在最后的 2 2 个记录中，比较个记录中，比较 1 1 次选出最小关键字的记录。次选出最小关键字的记录。 二、选择排序二、选择排序例例. . k1 k1 k2 k3 k4 k5 k6 k2 k3 k4 k5 k6 初始关键字：初始关键字： （4343 89 21 89 21 4343 28 15 28 15 ）

62、第第 1 1 遍排序后：遍排序后： 15 15 （89 21 89 21 4343 28 28 4343 ） 第第 2 2 遍排序后：遍排序后： 15 21 15 21 （89 89 4343 28 28 4343 ） 第第 3 3 遍排序后：遍排序后： 15 21 28 15 21 28 （4343 89 89 4343 ） 第第 4 4 遍排序后：遍排序后： 15 21 28 15 21 28 4343 （89 89 4343 ） 第第 5 5 遍排序后：遍排序后： 15 21 28 15 21 28 4343 43 43 89 89 二、选择排序二、选择排序算法分析算法分析 在任何情况下

63、，算法所需要的比较次数均为在任何情况下，算法所需要的比较次数均为 n-1 n-1 ( ( n n ) ) i=1 i=1 n(n-1)/2 n(n-1)/2 交换记录次数最多为交换记录次数最多为n-1n-1，移动记录数最多为移动记录数最多为3 3( (n-1)n-1)，在最好情况下，不在最好情况下，不移动记录。移动记录。 选择排序只需少量的中间变量作为辅助空间。算法是不稳定的选择排序只需少量的中间变量作为辅助空间。算法是不稳定的二、选择排序二、选择排序算法基本思想算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是将待排序的记录插入到已排序的子文件中去，使得插入

64、之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。序，前者使用顺序查找，后者使用折半查找。 ( (一一) )线性插入排序线性插入排序 设待排序的文件为设待排序的文件为( (R1R1，R2R2，RnRn),),关键字为关键字为( (R1.keyR1.key，R2.keyR2.key，RnRn.key).key

65、) 首先将初始文件中的记录首先将初始文件中的记录R1R1看作有序子文件。看作有序子文件。 第第1 1遍：遍： 将将R2R2插入这个有序子文件中插入这个有序子文件中：若：若R2R2的关键字小于的关键字小于R1R1的关键字，则的关键字，则R2R2插在插在 R1R1之之前；否则，前；否则，R2R2插在插在R1R1的后面。的后面。 第第 2 2 遍：遍： 将记录将记录R3R3插入前面已有插入前面已有2 2个记录的有序子文件中，得到个记录的有序子文件中，得到3 3个记录的有序子文件。个记录的有序子文件。 以此类推，依次插入以此类推，依次插入 R4R4，RnRn。最后得到最后得到 n n 个记录的升序文件

66、。个记录的升序文件。 三、插入排序三、插入排序 例例1. 1. 线性插入排序（线性插入排序（K0K0为临时工作单元，又称为临时工作单元，又称“监视哨监视哨”） K0 K1 K2 K3 K4 K5 K6 K0 K1 K2 K3 K4 K5 K6 初始关键字：初始关键字： 4343 21 89 15 21 89 15 4343 28 28 (43 (43后移后移) ) 第第 1 1 遍排序后：遍排序后： 21 ( 21 21 ( 21 4343 ) 89 15 ) 89 15 4343 28 28 ( (不后移不后移) ) 第第 2 2 遍排序后：遍排序后： 89 ( 21 89 ( 21 434

67、3 89 ) 15 89 ) 15 4343 28 28 (89,43,21 (89,43,21后移后移) ) 第第 3 3 遍排序后：遍排序后： 15 ( 15 21 15 ( 15 21 4343 89 ) 89 ) 4343 28 28 (89 (89后移后移) ) 第第 4 4 遍排序后：遍排序后： 43 ( 15 21 43 ( 15 21 4343 4343 89 ) 28 89 ) 28 (89,43,43 (89,43,43后移后移) ) 第第 5 5 遍排序后：遍排序后： 28 ( 15 21 28 28 ( 15 21 28 4343 4343 89 ) 89 ) 三、插入

68、排序三、插入排序算法分析：算法分析： 在最坏的情况下，对在最坏的情况下，对n n个记录线性插入排序大约需要个记录线性插入排序大约需要n(n-1)/2n(n-1)/2次比较。只需少量的中间变量作为辅助空间。次比较。只需少量的中间变量作为辅助空间。算法是稳定的算法是稳定的 三、插入排序三、插入排序( (二二) ) 折半插入排序折半插入排序 在插入排序过程中，因为由前面插入的记录已构成一个有序子文在插入排序过程中，因为由前面插入的记录已构成一个有序子文件，所以在插入件，所以在插入RiRi时，可以对这个有序子文件采用折半查找来确时，可以对这个有序子文件采用折半查找来确定定RiRi( (2 2，3 3，

69、n)n)的插入位置，以减少比较次数。这种插的插入位置，以减少比较次数。这种插入排序称为折半插入排序。入排序称为折半插入排序。 算法分析算法分析 折半插入排序的比较次数比线性插入排序的比较次数少；移动折半插入排序的比较次数比线性插入排序的比较次数少；移动记录的次数和辅助空间需求与线性插入排序法相同。记录的次数和辅助空间需求与线性插入排序法相同。四、归并排序四、归并排序基本思想基本思想 归并排序的基本思想是把归并排序的基本思想是把( ( 2) 2)个有序子文件组合在一起，形成一个新的有个有序子文件组合在一起，形成一个新的有序文件。同时归并个有序子文件的排序过程称为路归并排序。序文件。同时归并个有序

70、子文件的排序过程称为路归并排序。 2 2路归并路归并 例例1. 1. 将两个有序文件将两个有序文件 A A 和和 B B 归并为有序文件归并为有序文件 C C A A( 2( 2，1010，1515，1818，2121，30 ) 30 ) B B( 5( 5，2020，3535，40 ) 40 ) 按从小到大的次序从按从小到大的次序从 A A 或或 B B 中依次取出中依次取出 2 2、5 5、1010、1515、4040，顺序归并，顺序归并到到 C C 中，得中，得 C C( 2( 2，5 5，1010，1515，1818，2020，2121，3030，3535，40 ) 40 ) 2 2路

71、归并一般的过程路归并一般的过程 假定文件假定文件( ( rlrl，r(lr(l1)1)，rmrm，r(mr(m1)1)，r(mr(m2)2)，rhrh ) )中两个相邻的中两个相邻的有序子文件为有序子文件为( (rlrl，r(lr(l1)1)，rmrm) )和和( (r(mr(m1)1)，r(mr(m2)2)，rhrh) ) 其中，其中，lmhlmh。 现将这两个相邻的有序子文件归并为有序文件现将这两个相邻的有序子文件归并为有序文件( (ylyl，y(ly(l1)1)，yhyh ) )四、归并排序四、归并排序用用2 2路归并排序路归并排序 假假定定文文件件 1.1.n n 中中有有两两个个以以

72、上上的的有有序序子子文文件件，甚甚至至其其记记录录是是随随机机排排列列的的， 那那么么对对文文件件( ( 1, 1, 2, 2, ., ., n n ) )进进行行 2 2 路路归归并并排排序序时时，首首先先把把它它划划分分为为 长度均为长度均为1 1的的n n个有序子文件，然后对它们逐步进行个有序子文件，然后对它们逐步进行 2 2 路归并排序。其步骤如下：路归并排序。其步骤如下： 第第 1 1 遍：遍： 从从 1.1.n n 中中的的第第 1 1 个个和和第第 2 2 个个有有序序子子文文件件开开始始，调调用用归归并并相相邻邻有有 序序子子文文件件的的算算法法 ，每每次次归归并并两两个个相相

73、邻邻的的子子文文件件，归归并并结结果果 放放到到 1.1.n n 中中。此此时时，在在 1.1.n n 中中形形成成 n/2n/2 个个长长度度为为 2 2 的的有有序序子子文文件件。若若 n n 为奇数，则为奇数，则 中最后一个子文件的长度为中最后一个子文件的长度为 1 1。 第第 2 2 遍：遍： 把把 1.1.n n 看看作作输输入入文文件件，将将 n/2n/2 个个有有序序子子文文件件两两两两归归并并，归归并并结结果果回回送送到到 1.1.n n 中，在中，在 1.1.n n 中形成中形成 n/2n/2 /2/2 个长度为个长度为 4 4 的有序子文件。的有序子文件。 继续进行下去，共

74、计经过继续进行下去，共计经过 loglog2 2 n n 遍归并，最后得到遍归并，最后得到 n n 个记录的有序文件。个记录的有序文件。 四、归并排序四、归并排序例如，对例如，对1010个记录的个记录的 2 2 路归并排序，共计进行路归并排序，共计进行 loglog2 21010 4 4 遍归并。遍归并。 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 （9090）（）（7070）（）（8080）（）（6060）（）（5050）（）（4040）（）（3030）（）（2020）（）（1010）（）（100100） 第第 1

75、 1 遍归并排序：遍归并排序： k1 k2 k3 k4 k5 k6 k7 k8 k9 k10k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 1.101.10 （70 9070 90）（）（60 8060 80）（）（40 5040 50）（）（20 3020 30）（）（10 10010 100） 第第 2 2 遍归并排序：遍归并排序： k1 k2 k3 k4 k5 k6 k7 k8 k9 k10k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 1.101.10 （60 70 80 9060 70 80 90）（）（20 30 40 5020 30 40 50）（）（

76、10 10010 100） 第第 3 3 遍归并排序：遍归并排序： k1 k2 k3 k4 k5 k6 k7 k8 k9 k10k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 1.101.10 （20 30 40 50 60 70 80 9020 30 40 50 60 70 80 90）（）（10 10010 100） 第第 4 4 遍归并排序：遍归并排序： k1 k2 k3 k4 k5 k6 k7 k8 k9 k10k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 1.101.10 （10 20 30 40 50 60 70 80 90 100 10 20 30

77、40 50 60 70 80 90 100 ）四、归并排序四、归并排序 算法分析算法分析 归归并并排排序序比比前前面面讨讨论论的的几几种种排排序序方方法法的的速速度度都都要要快快。可可以以证证明明，对对 n n个个记记录录的的文文件件进进行行归归并并排排序序，所所需需比比较较关关键键字字的的次次数数不不超超过过 nlognlog2 2n n 数数量量级级，移移动动记记录录的的次次数数为为 nlognlog2 2n n。但但是是，归归并并排排序序需需要要一一个个大大小小为为 n n 的的辅辅助助空空间间，即即算算法法中中使使 用用的的数数组组。归归并并排排序是稳定的。序是稳定的。 五、快速排序五

78、、快速排序 基本思想：基本思想： 首先在待排序的文件首先在待排序的文件( ( 1 1，2 2，n )n )中，确定一个中，确定一个 i i，经过比较和移，经过比较和移，将将 i i 放到放到“中间中间”某个位置上，使得某个位置上，使得 i i 左边所有记录的关键字小于等于左边所有记录的关键字小于等于i i 的关键字，的关键字，i i 右边所有记录的关键字大于等于右边所有记录的关键字大于等于 i i 的关键字。于是，以的关键字。于是，以 i i所所在的位置为界，将文件划分为左、右两个子文件。然后，用同样的方法分别对这在的位置为界，将文件划分为左、右两个子文件。然后，用同样的方法分别对这两个子文件

79、进行划分，得到两个子文件进行划分，得到 4 4 个更小的子文件。继续进行下去，使得每个子文件个更小的子文件。继续进行下去，使得每个子文件只有一个记录为止，便得到原文件的有序文件。只有一个记录为止，便得到原文件的有序文件。 例如，给定文件例如，给定文件(20(20，1010，2222，8 8，4040，1616，1515，6060，18)18)，选用第，选用第1 1个元素个元素 20 20进行进行划分划分 x K1 K2 K3 K4 K5 K6 K7 K8 K9x K1 K2 K3 K4 K5 K6 K7 K8 K9 从从j j向左向左 20 20 10 22 08 40 16 15 60 18

80、 20 20 10 22 08 40 16 15 60 18 i j i j 五、快速排序五、快速排序 从从i i向右向右 20 18 10 22 08 40 16 15 60 18 20 18 10 22 08 40 16 15 60 18 i j i j 从从j j向左向左 20 18 10 22 08 40 16 15 60 22 20 18 10 22 08 40 16 15 60 22 i j i j 从从i i向右向右 20 18 10 15 08 40 16 15 60 22 20 18 10 15 08 40 16 15 60 22 i j i j 从从j j向左向左 20 1

81、8 10 15 08 40 16 40 60 22 20 18 10 15 08 40 16 40 60 22 i j i j 从从i i向右向右 20 18 10 15 08 16 16 40 60 22 20 18 10 15 08 16 16 40 60 22 i/j i/j (18 10 15 08 16) 20 (40 60 22) (18 10 15 08 16) 20 (40 60 22)五、快速排序五、快速排序 算法分析算法分析 就平均速度而言，快速排序是已知内部排序方法中最好的一种就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法。但是，在某种情况下，快速排序所需的比较次数和冒排序方法。但是，在某种情况下，快速排序所需的比较次数和冒泡排序的比较次数相同。泡排序的比较次数相同。 快速排序需要一个栈作辅助空间，用来实现递归处理左、右子快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。在最坏情况下，递归深度为文件。在最坏情况下，递归深度为 n n ，因此所需栈的空间大小为因此所需栈的空间大小为 n n 数量级。数量级。 快速排序是不稳定的。快速排序是不稳定的。