数据结构与算法分析期末复习ppt.ppt

《数据结构与算法分析期末复习ppt.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析期末复习ppt.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、“数数据据结构结构”复习复习指指导导2010.6考试说明考试说明本本课课程程为闭为闭卷考卷考试试考考试时间为试时间为120120分分钟钟。考考试题试题型型为为：选择题选择题（2020分）分）填填空空题题（2020分）分）判判断题断题（1010分）分）应应用用题题（2020分）（分）（选选做）做）算法算法题题（2020分）（分）（选选做）做）附加附加题题一、各章一、各章节节主要知主要知识识点点讲讲解解二、二、对对相相关关知知识识点的要求和点的要求和举举例例三、三、习题选讲习题选讲第1部分 绪论1.1.数据结构的基本概念数据结构的基本概念数据结构数据结构:是相互之间存在一种或多种特定关系的数据元素

2、是相互之间存在一种或多种特定关系的数据元素的集合，数据元素间的关系称为结构的集合，数据元素间的关系称为结构逻辑结构：数据元素间的逻辑（抽象）关系，与计算逻辑结构：数据元素间的逻辑（抽象）关系，与计算 机无关，同一种逻辑结构可以有不同的存机无关，同一种逻辑结构可以有不同的存 储结构（物理结构储结构（物理结构 例：链式例：链式 顺序）顺序）物理结构：数据的逻辑结构在计算机中的表示物理结构：数据的逻辑结构在计算机中的表示 （数据元素的表示和关系的表示）（数据元素的表示和关系的表示）第1部分 绪论4 4种基本的逻辑结构：种基本的逻辑结构：集合集合 线性（一对一）线性（一对一）树形（一对多）树形（一对多

3、）图形（多对多）图形（多对多）4 4种基本的物理结构：种基本的物理结构：顺序结构顺序结构链式结构链式结构散列结构散列结构索引结构索引结构习题集习题集P2 1.8P2 1.8（1 1，2 2，3 3）第1部分 绪论2.2.算法的基本概念算法的基本概念算法的算法的5 5个特性个特性:（有穷性、确定性、可行性、零个或（有穷性、确定性、可行性、零个或 多个输入、一个或多个输出）多个输入、一个或多个输出）时间复杂度：评估算法的重要标准之一，能较好的体现算时间复杂度：评估算法的重要标准之一，能较好的体现算 法本身的时间效率，与计算机硬件无关法本身的时间效率，与计算机硬件无关 （基本操作、问题的规模、基本操

4、作的频度是（基本操作、问题的规模、基本操作的频度是 问题规模的函数）问题规模的函数）例例:n:n个数中找最大的个数中找最大的习题集习题集P1 1.7P1 1.7（2 2，3 3）1.81.8（6 6，7 7）第2部分 线性表1.1.线性表的逻辑结构线性表的逻辑结构前驱、后继前驱、后继一对一的关系一对一的关系2.2.线性表的顺序存储结构（使用连续的存储空间）线性表的顺序存储结构（使用连续的存储空间）顺序表顺序表 特点：可以随机访问特点：可以随机访问插入插入:若有若有n n个元素的顺序表，在第个元素的顺序表，在第i i个元素之前插入，个元素之前插入，也即插入元素作为第也即插入元素作为第i i个元素

5、个元素 i=n+1 i=n+1时移动元素次数为时移动元素次数为0 0；i=1 i=1时移动元素次数为时移动元素次数为n n；一般情况一般情况n-i+1n-i+1；第2部分 线性表删除删除 i=1 i=1时时 移动元素次数为移动元素次数为n-1n-1；i=n i=n时移动元素次数为时移动元素次数为0 0；一般情况移动次数一般情况移动次数n-in-i；插入、删除的基本操作为元素移动插入、删除的基本操作为元素移动 时间复杂度为时间复杂度为O(nO(n)习题集习题集P4 2.7P4 2.7（1 1，2 2）当线性表的元素总数基本稳定，且很少进行插入和删除操当线性表的元素总数基本稳定，且很少进行插入和删

6、除操作，但要求以最快的速度存取线性表中的元素时，应采用作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。）存储结构。顺序表相关算法顺序查找、折半查找线性表中某个元素顺序查找、折半查找线性表中某个元素x x，返，返回其位置回其位置查找顺序表中某个元素查找顺序表中某个元素x x的个数的个数线性表的插入和删除算法线性表的插入和删除算法第2部分 线性表3.3.线性表的链式存储结构（存储空间可以连续也可以不连续）线性表的链式存储结构（存储空间可以连续也可以不连续）链表（结点、头指针、尾结点、带头结点的链表）链表（结点、头指针、尾结点、带头结点的链表）特点：不能随机访问特点：不能随机访问第2

7、部分 线性表4.4.单向链表单向链表静态法（说明变量）建立链表静态法（说明变量）建立链表尾插法建立链表（头指针、尾插法建立链表（头指针、q q始终指向尾结点、始终指向尾结点、p p生成新结点）生成新结点）头插法建立链表（头指针、头插法建立链表（头指针、q q始终指向头结点、始终指向头结点、p p生成新结点）生成新结点）插入（在第插入（在第i i个结点前插入新结点，个结点前插入新结点，p p生成新结点，生成新结点，q q指向第指向第 i-1 i-1个结点个结点）删除（删除第删除（删除第i i个结点，个结点，q q指向第指向第i i个结点的前驱（第个结点的前驱（第i-1i-1个结个结 点），点），

8、p p指向第指向第i i个结点）个结点）四种操作都必须知道操作位置结点的前驱结点的指针四种操作都必须知道操作位置结点的前驱结点的指针第2部分 线性表5.5.单向循环链表单向循环链表特点：从任一结点开始可以访问到表中其它结点，但特点：从任一结点开始可以访问到表中其它结点，但 不能随机访问不能随机访问由单向链表构造单向循环链表由单向链表构造单向循环链表如何判断单向循环链表如何判断单向循环链表6.6.双向循环链表双向循环链表l存储结构存储结构l特点特点l插入、删除插入、删除l习题集习题集P4 2.7P4 2.7（4 4，5 5，6 6）（单）链表的相关算法查查找找单链单链表中的最大表中的最大值值、最

9、小、最小值值查查找找单链单链表中元素表中元素x x的的个数个数分析以下语句的正误线线性表采用性表采用顺顺序存序存储储，必，必须须占用一片占用一片连续连续的存的存储单储单元。元。线线性表采用性表采用顺顺序存序存储储，便于，便于进进行行插插入和入和删删除操作。除操作。线线性表采用性表采用链链接存接存储储，不必占用一片，不必占用一片连续连续的存的存储单储单元。元。线线性表采用性表采用链链接存接存储储，便于，便于插插入和入和删删除操作。除操作。链表对于数据元素的插入和删除不需移动结点，只需改变链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的相关结点的指针域指针域的值。的值。第3部分 栈和队

10、列1.1.栈栈栈是运算受限的线性表栈是运算受限的线性表 插入、删除限定在表的尾部进行（栈顶）插入、删除限定在表的尾部进行（栈顶）栈顶、栈底、空栈、栈顶元素栈顶、栈底、空栈、栈顶元素顺序栈（连续的存储空间）顺序栈（连续的存储空间）用结构体变量实现的顺序栈用结构体变量实现的顺序栈 结构体变量结构体变量 规定：栈底为数组下标为规定：栈底为数组下标为0 0的一端的一端 溢出：栈顶指针（下标）为溢出：栈顶指针（下标）为-1-1时为空，栈顶为时为空，栈顶为MaxSize-1MaxSize-1时时 栈满栈满 上溢（满）、下溢（空）上溢（满）、下溢（空）数组（栈元素）数组（栈元素）整型变量（栈顶指针）整型变量

11、（栈顶指针）第3部分 栈和队列链栈（用链式存储结构实现的栈）链栈（用链式存储结构实现的栈）（了解）（了解）可以用不带头结点的单向链表实现链栈可以用不带头结点的单向链表实现链栈存储结构存储结构structstruct node*top node*top；基本操作：初始化、判栈空、进栈、出栈（与不带头基本操作：初始化、判栈空、进栈、出栈（与不带头 结点的单向链表的头部插入、头部删除相同）结点的单向链表的头部插入、头部删除相同）链栈只有空和非空两种状态，没有栈满的情况链栈只有空和非空两种状态，没有栈满的情况相关练习习题集 P5 3.1 3.2-2 3.5（1，3）3.3 3.4 3.6（15，16）

12、第3部分 栈和队列2.2.队列队列队列是运算受限的线性表队列是运算受限的线性表 允许在队尾插入，在队头删除允许在队尾插入，在队头删除队头、队尾、空队列队头、队尾、空队列 顺序队列（顺序存储的队列）顺序队列（顺序存储的队列）用结构体变量实现的顺序队列用结构体变量实现的顺序队列 结构体变量结构体变量数数组（队元素）元素）整型整型变量量1:front1:front（队头指指针）整型变量整型变量2:rear2:rear（队尾指针）（队尾指针）第3部分 栈和队列队列初始化：队头指针、队尾指针均置为队列初始化：队头指针、队尾指针均置为0 0队头指针队头指针frontfront指向队头元素指向队头元素队尾指

13、针队尾指针rearrear指向队尾元素的下一个位置指向队尾元素的下一个位置队列为空时队列为空时front=rearfront=rear队列满时队列满时rear=rear=MaxSizeMaxSize上溢：队列已满进行入队操作上溢：队列已满进行入队操作假上溢：队列未满，但尾指针已超越存储空间上界假上溢：队列未满，但尾指针已超越存储空间上界下溢：队列已空，要进行出队操作下溢：队列已空，要进行出队操作操作：初始化、判队空、入队、出队、取队头元素操作：初始化、判队空、入队、出队、取队头元素第3部分 栈和队列3.3.循环队列循环队列为解决为解决“假上溢假上溢”问题问题设想队列为一个首尾相接的圆环设想队列

14、为一个首尾相接的圆环为了区别循环队列的队满和队空规定少用一个存储空间为了区别循环队列的队满和队空规定少用一个存储空间 尾指针加尾指针加1 1等于头指针时为队满等于头指针时为队满 即即：（rear+1rear+1）%MaxSizeMaxSize=front=front 当当front=rearfront=rear时为队空时为队空第3部分 栈和队列4.4.链队列链队列（了解）（了解）可以用一个带头结点的单向链表存储队元素，可以用一个带头结点的单向链表存储队元素，在表头删除，在表尾插入在表头删除，在表尾插入存储结构：存储结构：structstruct node*front node*front，*r

15、earrear；基本操作基本操作 初始化、判队空、入队、出队初始化、判队空、入队、出队相关练习P6 3.5（8）栈和队列的特征栈和队列的异同点栈和队列的存储方式：顺序存储和链式存储第4部分 树和二叉树1.1.树的基本术语树的基本术语 叶结点（终端结点）、分支结点（非叶结点）叶结点（终端结点）、分支结点（非叶结点）结点的度（引出结点的个数）结点的度（引出结点的个数）孩子结点、双亲结点、兄弟结点孩子结点、双亲结点、兄弟结点 结点的层数、树的深度结点的层数、树的深度2.2.树的性质树的性质 性质性质1-1-性质性质5 5A AB BC CD DE EF FGGHHI I第4部分 树和二叉树性质性质1

16、 1 二叉树上第二叉树上第i i层至多有层至多有2 2i-1i-1个结点个结点性质性质2 2 深度为深度为h h的二叉树最多有的二叉树最多有2 2h h-1-1个结点个结点 1+2+4+8=21+2+4+8=24 4-1=15-1=15第4部分 树和二叉树性质性质3 3 二叉树上终端结点数等于双分支结点数加二叉树上终端结点数等于双分支结点数加1 1 （n0=n2+1n0=n2+1）要求：在结点总数、叶结点数、双分支结点数、单分要求：在结点总数、叶结点数、双分支结点数、单分支结点数之间能进行相关计算支结点数之间能进行相关计算A AB BC CD DE E第4部分 树和二叉树性质性质4 4含有含有

17、n n个结点的完全二叉树，其深度为个结点的完全二叉树，其深度为loglog2 2n n+1+1术语：满二叉树术语：满二叉树 完全二叉树完全二叉树第4部分 树和二叉树性质性质5 5二叉树中顺序编号为二叉树中顺序编号为i i的结点的结点左孩子：左孩子：2i2i右孩子：右孩子：2i+12i+1父结点：父结点：i/2i/2术语：满二叉树术语：满二叉树 完全二叉树完全二叉树相关练习习题集 P10 5.23（5-16）5.24（1，2，3，4，15-18）5.25（4，6，7，9，10，）第4部分 树和二叉树4.4.二叉树的存储结构二叉树的存储结构顺序存储顺序存储 树的序号与一维数组的下标对应树的序号与一

18、维数组的下标对应链接存储结构链接存储结构习题集习题集 P7 5.2P7 5.2left data right第4部分 树和二叉树5.5.二叉树的遍历二叉树的遍历递归定义：二叉树或者是一棵空树，或者是一棵由一递归定义：二叉树或者是一棵空树，或者是一棵由一个根结点和互不相交的分别称为根的左子树和右子树个根结点和互不相交的分别称为根的左子树和右子树所组成的非空树（左、右子树可以为空树），左、右所组成的非空树（左、右子树可以为空树），左、右子树也同样是一棵二叉树子树也同样是一棵二叉树习题集习题集P8 5.7 P8 5.7 C CB BA A第4部分 树和二叉树遍历：按照一定次序访问每个结点一次且仅一次

19、遍历：按照一定次序访问每个结点一次且仅一次遍历规则：遍历规则：（先左后右，以访问根的次序区分遍历方法）（先左后右，以访问根的次序区分遍历方法）先序：根、左子树、右子树先序：根、左子树、右子树 中序：左子树、根、右子树中序：左子树、根、右子树 后序：左子树、右子树、根后序：左子树、右子树、根递归算法程序（掌握）递归算法程序（掌握）例例 后序遍历：后序遍历：5,4,2,6,9,8,7,3,1 5,4,2,6,9,8,7,3,11 12 23 34 46 67 75 58 89 9第4部分 树和二叉树 例例 中序遍历：中序遍历：CBDAEGFCBDAEGF 先序遍历：先序遍历：ABCDEFGABCD

20、EFG 后序遍历：后序遍历：CDBGFEACDBGFEA二叉树的非递归遍历算法（了解）二叉树的非递归遍历算法（了解）二叉树的其它运算（了解）二叉树的其它运算（了解）A AB BE EC CD DF FGG第4部分 树和二叉树6.6.哈夫曼树哈夫曼树结点的带权路径长度（路径长结点的带权路径长度（路径长结点的权）结点的权）树的带权路径长度树的带权路径长度 WPL=WPL=WPL=WPL=WiLiWiLiWiLiWiLi 所有叶结点的带权路径长度之和：所有叶结点的带权路径长度之和：4x3 4x32x2+1x1=2x2+1x1=12 24第4部分 树和二叉树哈夫曼树（最优树）哈夫曼树（最优树）n n个

21、带权叶结点的所有二叉树中，个带权叶结点的所有二叉树中，WPLWPL最小的树最小的树 性质：除叶结点外其余结点全为双分支结点（要求掌性质：除叶结点外其余结点全为双分支结点（要求掌握哈夫曼树总结点数、叶结点数、分支结点数之间的握哈夫曼树总结点数、叶结点数、分支结点数之间的计算）计算）构造构造HuffmanHuffman树和树和HuffmanHuffman编码编码习题集习题集 P8 5.14 5.15P8 5.14 5.15（总码数不要求）（总码数不要求）第4部分 树和二叉树例：权重：例：权重：a,b,c,d,ea,b,c,d,e 3,5,6,7,9 3,5,6,7,9 a:000 a:000 b:

22、001 b:001 c:10 c:10 d:11 d:11 e:01 e:013030171713138 89 96 67 73 35 5000001111第4部分 树和二叉树7.7.由遍历序列确定二叉树由遍历序列确定二叉树先序先序 中序（先序确定根结点，中序划分左右子树）中序（先序确定根结点，中序划分左右子树）后序后序 中序（后序确定根结点，中序划分左右子树）中序（后序确定根结点，中序划分左右子树）例例 先序遍历序列为先序遍历序列为stuwvstuwv，中序遍历序列为，中序遍历序列为uwtvsuwtvs 由先序：由先序：s s是根，是根，由中序：左子树由中序：左子树uwtvuwtv，右子树为

23、空，右子树为空 由先序：由先序：t t是左子树根，由中序：左子树是左子树根，由中序：左子树uwuw，右子树，右子树v v 由先序：由先序：u u是左子树根，由中序：左子树空，右子树是左子树根，由中序：左子树空，右子树w ws st tu uw wv v第4部分 树和二叉树例：先序遍历：例：先序遍历：bfdecbfdec，中序，中序fbedcfbedc 由先序：由先序：b b为根为根 由中序：左子树由中序：左子树f f，右子树，右子树edcedc 由先序：由先序：d d为根为根 由中序：左子树由中序：左子树e e，右子树，右子树c c 后序：后序：fecdbfecdb习题集习题集P8 5.13P

24、8 5.13及其类似的题必须掌握及其类似的题必须掌握b bf fe ed dc c第5部分 查找1.1.基本概念基本概念平均查找长度平均查找长度 查找的基本操作是查找的基本操作是“比较比较”ASL=ASL=ASL=ASL=CiPiCiPiCiPiCiPi:CiCiCiCi是查找到第是查找到第是查找到第是查找到第i i i i个记录的比较次数个记录的比较次数个记录的比较次数个记录的比较次数 Pi Pi Pi Pi是查找第是查找第是查找第是查找第i i i i个记录的概率个记录的概率个记录的概率个记录的概率第5部分 查找2.2.线性表的查找线性表的查找顺序查找：等概率条件下顺序查找：等概率条件下

25、ASL=1/n i=(n+1)/2ASL=1/n i=(n+1)/2折半查找和折半查找对应的判定树折半查找和折半查找对应的判定树 要求：查找表（顺序存储要求：查找表（顺序存储)中记录相应的关键字值必须中记录相应的关键字值必须有序（升序或降序）有序（升序或降序）例：查找表例：查找表6,14,20,21,38,56,68,78,85,85,1006,14,20,21,38,56,68,78,85,85,100 序号序号 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 第5部分 查找（1 1）画出折半查找的判定树）画出折半查找的判定树（2 2）查找到）查找

26、到6868要进行多少次元素间的比较（要进行多少次元素间的比较（3 3次）次）（3 3）要查）要查3232，经多少次查找确定查不到（，经多少次查找确定查不到（4 4次）次）（4 4）等概率条件下，平均查找长度）等概率条件下，平均查找长度 ASL=(1X1+2X2+3X4+4X4)/11=ASL=(1X1+2X2+3X4+4X4)/11=判定树：判定树：习题集习题集 P13 6.1P13 6.18 80 03 36 69 91 14 410107 7383820206 685852121686885851414565678781001005 52 2第5部分 查找3.3.分块查找分块查找查找表分块

27、：块间有序、每块无序查找表分块：块间有序、每块无序索引表：索引表中一个记录对应一块索引表：索引表中一个记录对应一块查找步骤：折半查找确定块，块内顺序查找查找步骤：折半查找确定块，块内顺序查找 块内最大关键字块内最大关键字块中第一个记录的位置（地址指针）块中第一个记录的位置（地址指针）索引表记录索引表记录静态查找方法比较静态查找方法比较ASL最大最大最小最小两者之间两者之间表结构表结构有序表有序表/无序表无序表 有序表有序表分块有序表分块有序表存储结构存储结构 顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构顺序存储结构顺序存储结构线性链表线性链表顺序查找顺序查找折半查找折半查找

28、 分块查找分块查找第5部分 查找4.4.动态查找动态查找二叉排序树二叉排序树 三要素：三要素：（a a）根结点大于左子树上所有结点的值（或等于）根结点大于左子树上所有结点的值（或等于）（b b）根结点小于右子树上所有结点的值（或等于）根结点小于右子树上所有结点的值（或等于）（c c）左、右子树也分别是一棵二叉排序树）左、右子树也分别是一棵二叉排序树 例：二叉排序树的充分必要条件是其任一结点的值均大例：二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值（于其左孩子的值、小于其右孩子的值（x x）3 35 56 65 51 12 24 4第5部分 查找二叉排序树的插入操作

29、（也可用来构造二叉排序树）二叉排序树的插入操作（也可用来构造二叉排序树）例例:(1):(1)给定序列给定序列9,18,6,10,22,11,8,20,7,9,18,6,10,22,11,8,20,7,依次取序依次取序 列中的数构造一棵二叉排序树列中的数构造一棵二叉排序树 (2)(2)给出中序遍历的序列给出中序遍历的序列 6,7,8,9,10,11,18,20,22 6,7,8,9,10,11,18,20,226 6181822228 810109 91111 20207 7第5部分 查找对二叉排序树进行中序遍历所得的序列是有序序列对二叉排序树进行中序遍历所得的序列是有序序列 (由小到大）由小到

30、大）二叉排序树的删除操作（分二叉排序树的删除操作（分4 4种情况，了解）种情况，了解）删除原则是删除后使得到的树是二叉排序树删除原则是删除后使得到的树是二叉排序树习题集习题集 P13 6.3P13 6.3 第5部分 查找平衡二叉树（平衡二叉树（AVLAVL树）树）平衡因子的绝对值小于等于平衡因子的绝对值小于等于1 1四种旋转方式四种旋转方式习题集习题集 P13 6.5 P13 6.5 以及以前的作业题以及以前的作业题 第5部分 查找5.5.哈希表及其查找哈希表及其查找相关名词相关名词 哈希函数：记录的关键字哈希函数：记录的关键字 存储地址存储地址 哈希表：存放查找表中记录的序列，存储位置是以关

31、哈希表：存放查找表中记录的序列，存储位置是以关键字为自变量由哈希函数计算所得到的数值键字为自变量由哈希函数计算所得到的数值 哈希查找（散列查找）原理：哈希查找（散列查找）原理：在待查记录的关键字值与该记录的存储位置之间建立在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系确定的对应关系哈希函数构造法、处理冲突的方法哈希函数构造法、处理冲突的方法除留余数法除留余数法开放定址法和链地址法开放定址法和链地址法哈希查找的练习题散列查找法的特点是（）。A、通过关键字的比较进行 B、通过关键字计算元素的存储地址进行查找 C、通过关键字计算元素的存储地址并进行一定的比较进行查找 D、以上都不是 习

32、题集P13 6.8 6.11（17，20）练习题以前做过的题目，如第6部分 排序1.1.基本概念基本概念排序排序稳定的排序方法稳定的排序方法 关键字相等的记录经排序后保持它们原来的前后关系关键字相等的记录经排序后保持它们原来的前后关系不稳定的排序方法不稳定的排序方法 关键字相等的记录经排序后可能改变它们原来的前后关键字相等的记录经排序后可能改变它们原来的前后关系关系第6部分 排序2.2.插入类排序插入类排序直接插入排序：每一趟从无序子表中将一个待排的记直接插入排序：每一趟从无序子表中将一个待排的记录按其关键字大小放到已排好序的子序列的适当位置录按其关键字大小放到已排好序的子序列的适当位置 例例

33、 47,83,41,53,6847,83,41,53,68 47 47 47,83 47,83 41 47 83 41 47 83 41 47 53 83 41 47 53 83 41 47 53 68 8341 47 53 68 83第6部分 排序例：例：6565，4949，116116，4343，2626，9292，8080，5555，100100用直接插用直接插入排序，当要把第入排序，当要把第7 7个元素个元素8080插入到已排好序的子表时，插入到已排好序的子表时，需进行多少次元素的比较需进行多少次元素的比较 26 43 49 65 92 116|80 26 43 49 65 92 11

34、6|80 3 3次次 第6部分 排序折半插入排序折半插入排序 利用折半查找寻找插入位置利用折半查找寻找插入位置第6部分 排序希尔排序希尔排序 按照一定的增量逐步缩小范围进行排序按照一定的增量逐步缩小范围进行排序 在增量范围内进行直接插入排序即可在增量范围内进行直接插入排序即可要求能够写出希尔排序的每一趟要求能够写出希尔排序的每一趟第6部分 排序3.3.交换类排序交换类排序冒泡排序冒泡排序 n n个元素，从左到右两两比较，必要时交换个元素，从左到右两两比较，必要时交换 共需要共需要n-1n-1趟冒泡趟冒泡 第第i i趟要进行趟要进行n-in-i次元素间比较次元素间比较 若某一趟冒泡中没有进行元素

35、的交换（若某一趟冒泡中没有进行元素的交换（0 0次交换），则次交换），则序列已排好序序列已排好序第6部分 排序快速排序快速排序 选取划分元素，选取划分元素，i i，j j分别指向序列起、止位置，分别指向序列起、止位置，从后向前从后向前(j)(j)扫描找到小于分割元素的元素，扫描找到小于分割元素的元素，占位占位(i),i=i+1;(i),i=i+1;从前向后从前向后(i)(i)扫描找到大于分割元素的元素，扫描找到大于分割元素的元素，占位占位(j),j=j-1;(j),j=j-1;i i等于等于j j时完成一趟快速排序时完成一趟快速排序要求写出快速排序的第一趟要求写出快速排序的第一趟第6部分 排序

36、例例 55,50,75,53,45,105 55,50,75,53,45,105 55 55 55 55，5050，7575，5353，4545，105105 45 45，5050，7575，5353，4545，105 105 从后向前从后向前 45 45，5050，7575，5353，7575，105 105 从前向后从前向后 45 45，5050，5353，5353，7575，105 105 从后向前从后向前 45 45，5050，5353，5555，7575，105105(55(55归位归位)第6部分 排序4.4.选择类排序选择类排序直接选择排序直接选择排序 第第1 1趟：让趟：让a1a

37、1与与a2a2 anan 比较找到最小元素的下标比较找到最小元素的下标 k k1 1，让，让a1a1与与akak1 1 交换交换 第第2 2趟：让趟：让a2a2与与a3a3 anan 比较找到最小元素的下标比较找到最小元素的下标 k k2 2，共进行共进行n-1n-1趟选择趟选择第6部分 排序堆排序堆排序堆和特殊性质完全二叉树的对应堆和特殊性质完全二叉树的对应例：堆例：堆14,40,30,50,80,65,50,10014,40,30,50,80,65,50,100 1414404030305050808065655050100100第6部分 排序小根堆：任意非叶结点的值小于等于左、右孩子结点

38、的值小根堆：任意非叶结点的值小于等于左、右孩子结点的值大根堆：任意非叶结点的值大于等于左、右孩子结点的值大根堆：任意非叶结点的值大于等于左、右孩子结点的值筛选法建堆筛选法建堆 例：序列例：序列47,87,72,107,21,37,62,5747,87,72,107,21,37,62,574747107107212137376262575772728787474757572121727262621071073737878747475757878772726262107107373721212121575787877272626210710737374747（初始树）（初始树）（堆）（堆）第6部分

39、 排序堆排序：用筛选法建堆排序：用筛选法建n n个元素的堆，交换堆顶元素和最个元素的堆，交换堆顶元素和最后一个元素，再用筛选法建后一个元素，再用筛选法建n-1n-1个元素的堆个元素的堆能画出初始堆和最大、小堆能画出初始堆和最大、小堆如何排序，排出第一、二个如何排序，排出第一、二个第6部分 排序5.5.归并排序归并排序归并两个有序的序列（指针法）归并两个有序的序列（指针法）一趟归并排序一趟归并排序归并排序归并排序归并排序原理归并排序原理 （1 1，1 1）归并得到若干长度为）归并得到若干长度为2 2的有序序列的有序序列 （2 2，2 2）归并得到若干长度为）归并得到若干长度为4 4的有序序列的有序序列 第6部分 排序例例 40,35,55,25,70,100,30,7540,35,55,25,70,100,30,75 35,4025,5570,10030,75 35,4025,5570,10030,75 25,35,40,5530,70,75,100 25,35,40,5530,70,75,100 25,30,35,40,55,70,75,100 25,30,35,40,55,70,75,100习题集习题集 P15 7.2 P15 7.2 P16 7.9 P16 7.9（1010，1515）7.107.10（9-119-11，2424，2626）祝同学们取得好成绩！