复旦大学软件工程考研(MSE)数据结构复习资料.pptx

数据结构2016MSE考研冲刺 1课程安排n课程介绍n栈、队列和向量 n树n查找n排序n图2课程目的n（以最小代价）通过考试！n不是成为专家n不是初学授课3试题结构n考试满分60分n考试题型：问答、分析、编程4样题问答和编程题n插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是_n试论述什么叫Hash冲突及有那些处理方法n编程实现对二叉树所有节点的统计5课程安排n课程介绍n栈、队列和向量 n树n查找n排序n图6链表、栈和队列n大纲描述：q单链表,双向链表,环形链表,带哨兵节点的链表q栈的基本概念和性质,栈ADT及其顺序,链接实现;栈的应用;栈与递归;q队列的基本概念和性质,队列ADT及其顺序,链接实现;队列的应用;q向量基本概念和性质;向量ADT及其数组、链接实现;7线性表基本概念和性质n线性表q是n个数据元素的有限序列q常见线性表包括数组、链表、栈、队列等n线性表的两种实现方式q顺序q链式q对比：插入（有序、无序）、删除、查找、读取8环形链表n环形链表q又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点9栈的基本概念和性质n栈：q栈是限定仅在表尾进行插入和删除操作的线性表q后进先出特性（LIFO）q栈顶、栈底、出栈、入栈10例题n设有一个栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则栈的容量至少应为多少？n答案：311栈的基本概念和性质n设计递归问题的非递归算法一般需要用到栈机制n三个数a、b、c进栈，不可能出现c、a、b顺序出栈12例题n若某栈的输入序列为a、b、c，则所有可能的出栈序列有_种，所有不可能的出栈序列有_种。n答案：5，113例题n若栈的输入序列为1,2,3,4，则是不可能的栈输出序列之一。n答案：4，3，1，214习题n若某栈的输入序列为a、b、c、d，则所有可能的出栈序列有_种，所有不可能的出栈序列有_种。n请写出所有可能的序列和不可能的序列。15栈的应用n数制转换q十进制数字与d进制数字的转换qN=(N div d)d+N mod d其中div为整除，mod为求余。q算法：n将算法3.1中8换成d16例题n十进制数1167等于八进制数？n答案：2217n思路：q计算方法：除余倒排法q验证方法：指数相加法17习题n十进制数1167等于七进制数？18栈的应用n表达式求值：q中缀表达式转后缀表达式q后缀表达式求值n三种表达式：q前缀表达式+a bq中缀表达式 a+bq后缀表达式 a b+19例题n中缀表达式a+b c d转为后缀表达式是？n答案：a b cd20例题n中缀表达式（a+b）c d转为后缀表达式是？n答案：a b cdn思路：q数字位序不变，运算符位置改变q后缀表达式无括号，运算顺序同中缀表达式21习题n中缀表达式A-(B+C)*D/E的后缀形式是_。22练习n中缀表达式a*(b+c)/d转为后缀表达式是？23例题n计算后缀表达式1 2+4*2/的值为？n答案：6n思路：q顺序计算q或 转换为中缀表达式计算24习题n计算后缀表达式3 2 4*2/3的值为？25递归n一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数q优点：结构清晰、程序易读、正确性容易得到证明q缺点：效率相对较低26队列的基本概念和性质n队列：q队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表q先进先出特性（FIFO）q队尾、队头、入队、出队27例题n在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是，队尾元素是。n答案：c，d28双向队列n双向队列：q亦称双端队列（Deque）q是限定插入和删除操作在表的两端进行的线性表q可以用于包装产生栈和队列29课程安排n课程介绍n栈、队列和向量 n树n查找n排序n图30树 n大纲描述：q树的基本概念和术语；树的前序、中序、后序、层次序遍历；q二叉树及其性质；普通树与二叉树的转换；q树的存储结构,标准形式;完全树(complete tree)的数组形式存储;q树的应用，Huffman树。31树的基本概念和术语n树：q是n（n0）个结点的有限集q在任意一棵非空树中：1.有且仅有一个特定的称为根的结点2.当n1时，其余结点可以分为m（m0）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树q树属于层次结构数据结构32树的基本概念和术语n节点n标签n父节点、子节点、兄弟节点、祖先节点、子孙节点n路径、树枝n根、叶子n次数n内部节点、外部节点n树的次数、K次树n节点层次、树的高度和深度n子树n有序树、无序树n森林、果园33例题34例题n列出如上图所示树的所有叶子结点q答案：K,L,F,G,M,I,Jn列出如上图所示树的所有分支结点q答案：A,B,C,D,E,Hn树A为几次树？子树B呢？q答案：3，2n前页图所示树的高度为多少？q答案：435树的基本概念和术语n如果将树中结点的各子树看作从左到右有序的,则该树为有序树(ordered tree),否则为无序树。n森林(forest)是m棵互不相交的树的集合。n如果把一棵树的根砍去，剩下的部分就是森林。n如果原来的树是有序的,则砍去根后的森林也是有序的,此时称该森林为有序森林或果园。36二叉树及其性质n二叉树（Binary Tree）q另一种树形结构，特点是每个结点至多只有二棵子树，且子树有左右之分，其次序不能任意颠倒n二叉树可能的五种基本形态37二叉树及其性质n在二叉树的第i层上至多有2i1个结点（i1）38例题n一棵二叉树第五层上至多有多少个结点？至少多少？n答案：16，139二叉树及其性质n深度为k的二叉树至多有2k1个结点（k1）40例题n深度为n(n0)的二叉树最多有_个结点。n答案：2n-141例题n一棵深度为5的二叉树至多有多少个结点？至少多少？n答案：31，542例题n高度为h(h0)的二叉树最少有_个结点？n答案：h43二叉树及其性质n对于任何二叉树,如果叶子节点数为n0,度为2的节点数为n2,则n0=n2+144例题n在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n2=_。n答案：n0 145例题n若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_。n答案：946例题n若一二叉树有2度结点100个，则其叶结点有多少个？n答案：10147例题n若二叉树中度为2的结点有15个，度为1的结点有10个，共有多少个结点？n答案：4148例题n在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有_个叶结点。n答案：6n构造法49二叉树及其性质n满二叉树：q一棵深度为k且有2k1个结点的二叉树q可以对满二叉树的结点进行连续编号，约定编号从根开始，自上而下，自左而右。n完全二叉树：q深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。50二叉树及其性质n完全二叉树特点：q叶子结点只可能出现在层次最大的两层上q对任一结点，若其右分支下子孙的最大层次为l，其左下分支的子孙的最大层次必为l或者l1。n深度为k的完全二叉树第k层最少1个结点，最多2k-1-1个结点；整棵树最少2k-1个结点，最多2k-2个结点51例题n若某完全二叉树的深度为h，则该完全二叉树中至少有_个结点。n答案：2h-152例题n若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。n答案：25-1+33453例题n一个具有767个结点的完全二叉树，其叶子结点个数为_。n答案：384n分析：可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n=n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0（n1）/2，就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得：384。54二叉树及其性质n具有n个结点的完全二叉树的深度为log2n+155例题n具有2000个结点的二叉树，其深度至少为_。n答案：1156二叉树及其性质n如果含有n 1个节点的二叉树的高度为log2n1,将其所有结点按层次序编号,则对于任一节点j(1j n),有q如果j=1,则节点j是树的根,无双亲;如果j1,则其父节点parent(j)是节点j/2q如果2jn,则节点j无左子节点;否则其左子节点为2jq如果2j+1n,则节点j无右子节点;否则其右子节点为2j+1n证明57完全树的数组形式存储n完全树的数组形式存储算法q将其编号为i的结点元素存储在一维数组下标为i1的分量中58例题n已知数组20,30,19,87,30,40表示一棵完全二叉树，请画出该树。59练习答案60树的遍历n树的遍历 q按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅且一次q二叉树的遍历可分为前序、中序、后序、层次序等q普通树的遍历可以分为先根、后根、层次序等61树的遍历n二叉树的遍历q前序、中序、后序定义q层次序：从上而下，从左至右n常见问题q已知树写遍历结果q已知遍历结果画树n依据：二叉树的前序和中序遍历可以唯一确定一棵二叉树n思路：前序定根，中序定左右q递归和非递归算法实现62例题n写出左图所示二叉树的前序、中序、后序、层次序遍历结果63例题答案n前序：ABDCEFGn中序：DBAECFGn后序：DBEGFCAn层次序：ABCDEFG64例题n假设一棵二叉树的前序遍历为EBADCHGFIKJ，中序遍历为ABCDEFGHIJK，请画出该树。65例题答案66树的遍历n普通树的遍历q前根：先遍历根结点，再依次前根遍历各棵子树q后根：先后根遍历各课子树，再遍历根结点q已知树写遍历结果q已知遍历结果画树n思路：先根定根，后根定子树67例题n写出如右图所示树的先根、后根、层次序遍历结果68例题答案n前序：ABECFGHDn后序：EBFHGCDAn层次序：ABCDEFGH69练习给出如图所示树的先根、后根和层次序遍历结果70练习答案n前根：ABEFHIGCJKLDMNOQPn后根：EHIFGBKLJCNQOPMDAn层次序：ABCDEFGJMHIKLNOPQ71例题n画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ树的后根次序访问序列为DIAEKFCJHBG72例题答案73普通树与二叉树的转换n对于任意k次树到相应二叉树的转换算法q对于具有子节点n1,n2nk的节点n,将n1作为其左子节点,且kj+1作为kj(1 j k-1)的右子节点n思路：“不同层在左，同层在右”74普通树与二叉树的转换n对于任意森林到相应二叉树的转换算法为 q设T=(T1,T2.Tm)为m(m0)棵树的序列,而BT(T1,T2.Tm)为相应的二叉树,则n如果m=0,则BT为空树n如果m0,则T1的根节点就是BT的根节点,而BT的左子树是T1的子树T11,T12T1K转换成的BTl(T11,T12T1K),其右子树为BTr(T2.Tm)75例题n将下页图所示森林转换为等价的二叉树76例题77例题答案78练习将如图所示树转换为二叉树79练习答案80Huffman树nHuffman树：q又称最优树，是一类带权路径长度最短的树n基本概念：q树的路径长度：从根到每一结点的路径长度之和。q结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。q树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做WPL。81Huffman树n基本概念：q假设有n个权值wi，试构造一棵有n个叶子结点的二叉树，每个叶子的结点带权为wi，则其中WPL最小的二叉树称为最优二叉树或赫夫曼树n算法q见下页82Huffman算法(1)由给定的n个权值w0,w1,w2,wn-1，构造具有n棵二叉树的集合F=T0,T1,T2,Tn-1，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。(2)在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。(3)在F中删去这两棵二叉树，加入新得的树。(4)重复(2)(3)，直到F只含一棵树为止。这棵树就是赫夫曼树83ZKFCUDL E2724323742421202Z7K24F32C37U42D42L120EStep 12Z7K24F32C37U42D42L120E92Z7K24F32C37U42D42L120E933Round 1Round 2例题842Z7K24F32C37U42D42L120E93365Round 3852Z7K24F32C37U42D42L120E9336579Round 4862Z7K24F32C37U42D42L120E9336579107Round 5872Z7K24F32C37U42D42L120E9336579107186Round 6882Z7K24F32C37U42D42L120E9336579107186306Round 7(final)89Huffman编码n编码：等长编码/不等长编码n前缀编码：若要设计长短不等的编码，则必须是任一个字符的编码抖不是另一个字符编码的前缀，这种编码叫做前缀编码nHuffman编码：以n种字符出现的频率做权，设计一棵赫夫曼树，由此得到的前缀编码称为Huffman编码90例题LetterFreqCodeBitsC3211104D421013E12001F24111115K71111016L421103U371003Z211110062Z7K24F32C37U42D42L120E93365791071863060000011111100191习题n某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率是0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11。构造以字符使用频率为权值的Huffman树，并给出相应的Huffman编码。92习题答案93习题答案nA：0110nB：10nC：1110nD：1111nE：110nF：00nG：0111nH：01094课程安排n课程介绍n栈、队列和向量 n树n查找n排序n图95查找 n大纲描述：q查找的基本概念；对线性关系结构的查找，顺序查找，二分查找；qHash查找法,常见的Hash函数(直接定址法,随机数法),hash冲突的概念,解决冲突的方法(开散列方法/拉链法,闭散列方法/开址定址法),二次聚集现象;qBST树定义,性质,ADT及其实现,BST树查找,插入,删除算法;q平衡树(AVL)的定义,性质,ADT及其实现,平衡树查找,插入算法,平衡因子的概念;q优先队列与堆,堆的定义,堆的生成,调整算法;范围查询;96查找的基本概念n查找表(search table)：q具有同一类型数据元素(经常称为记录)的集合n查找表的基本操作有：q查找某个“特定”记录是否在表中q查找到后取出某个“特定”记录的各个数据项q向表中插入记录q从表中删除记录97查找的基本概念n静态查找表(static search table)：q仅用于查询的查找表。n动态查找表(dynamic search table):q若在查找过程中需同时插入表中不存在的记录;或者需要删除记录,则称之为动态查找表。n关键字/键值(key)：q记录某个数据项的值,用其可以标示该记录q当记录只有一个数据项时,其关键字即为该记录的值q如果一个key可以唯一标示一个就,则称之为主关键字(primary key),否则称之为次关键字(secondary key)98查找的基本概念n查找(search)：q在一个查找表中找出具有“特定”键值的那些记录q所谓查找成功是指在查找表中找到了满足条件的记录,此时一般会返回找到的记录,或者返回记录的位置信息,或者仅仅返回找到(true)q否则称为查找失败,此时一般返回空指针,或特殊值,或者仅仅返回没有找到(false),有时也会就此插入这个元素99BST树定义，性质，实现n二叉排序树(Binary Sorted Tree)q又称二叉搜索树或二叉查找树q或者是一棵空树；q或者是具有下列性质的二叉树：n如果左子树非空,则左子树中所有节点的键值均小于它的根结点的值；n如果右子树非空,则右子树中所有节点的键值均大于它的根结点的值；n它的左右子树也都是二叉排序树。100BST树定义，性质，实现n二叉排序树性质 q如果对二叉排序树进行中序遍历,则得到一个从小到大排好序的列表,所以可以得到一种简单的排序方法叫做“树排序”(treesort)。q我们也可以根据这个性质定义二叉排序树为:如果一棵树按中序遍历为排好序的,则这棵树是二叉排序树。101BST树查找，插入，删除算法nBST树查找，插入，删除算法q画图q算法102例题n已知BST树如左，请画出插入16，再删除36之后的BST树103例题答案104例题n试求按关键字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树105例题答案106练习n假设结点序列F（60，30，90，50，120，70，40，80），试用BST的插入算法，用F中的结点依次进行插入，画出由F中结点所构成的BST树T1；再用删除算法，依次删除40，70，60，画出删除后的BST树T2。107练习答案108平衡树n平衡因子（balanced factor）q二叉树上任一节点的左子树高度减去右子树高度的差nAVL Tree，根据其三位发明者(Adelson-Velskii and Landis)的名字命名n一棵BST树中每个节点平衡因子的绝对值不超过1109平衡树n基本思想:q在插入或删除节点后对新树进行判断,如果新树已经变得不平衡,则通过旋转(rotation)的方法对树进行重组/改组(re-arrange),使得重组后的树在保持查找树特性的同时保持平衡n所谓旋转:q通过改变支撑点来维持平衡q顺时针旋转为右旋;逆时针旋转为左旋q可以进行连续的多次旋转110平衡树111算法代码及基本的时间复杂度分析查找方法查找方法平均时间平均时间顺序查找O(n)二分查找O(logn)BST查找O(logn)AVL查找O(logn)112Hash查找法，常见的Hash函数n哈希（Hash）函数：q在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。这个对应关系f为哈希函数。按这个思想建立的表为哈希表。q哈希函数的设定可以很灵活，只要使得任何关键字的哈希函数值都落在表长允许范围之内即可。113Hash查找法，常见的Hash函数n练习：q已知线性表关键字集合为：S=and,begin,do,end,for,go,if,repeat,then,until,while，求哈希函数。n答案：qH(key)=key0 a;即为关键字key中的第一个字母在字母表a,b,c,.,z中的序号114Hash查找法，常见的Hash函数n直接定址法q直接取key或者key的某个线性函数值 h(key)=a*key+b,a,b为常数q如前面的例子,又如人口普查时使用年龄,出生年份等115Hash查找法，常见的Hash函数n除留余数法q选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即：H(key)=key%Pq方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。q缺点:n整数相除速度较慢116Hash查找法，常见的Hash函数n如:m=8，16，32，64，128，256，512，1024P =7，13，31，61，127，251，503，1019117解决冲突的方法n对不同的关键字可能得到同一哈希地址，这种现象称冲突。具有相同函数值的关键字对该哈希函数来说称作同义词。n在一般情况下，冲突只能尽可能的少，而不能完全避免。118解决冲突的方法n共同思想:将具有相同函数值的记录存作一个链n闭散列方法/开址定址法q冲突记录存储在表内n开散列方法/链地址法q冲突记录存储在表外119解决冲突的方法n基本思想q当冲突发生时，使用某种方法在散列表中形成一个探查序列(也称之为链)，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。qHj=(H(key)+dj)MOD m n1 j m-1;m为hash表长度ndj为增量数列,各种方法的不同就区别在取不同的增量数列上120解决冲突的方法n常用的增量数列:q线性探测法q二次探测法q伪随机法q再哈希法/二次哈希法q桶式散列法121解决冲突的方法n线性探测法q取dj=1,2,m-1q将散列表看成是一个环形表。若地址为d（即H(key)=d）的单元发生冲突，则依次探查下述地址单元：d+1，d+2，.，m-1，0，1，.，d-1,直到找到一个空单元或查找到关键字为key的结点为止。若沿着该探查序列查找一遍之后，又回到了地址d，则无论是做插入操作还是做查找操作，都意味着失败。122解决冲突的方法n线性探测法q缺点:n特别容易产生聚集n链非常长123解决冲突的方法n拉链法q若选定的散列函数的值域为0到m-1，则可将散列表定义为一个由m个单链表的链表头指针组成的指针数组HTP(m)，凡是散列地址为i的结点，均插入到以HTP(i)为头指针的单链表中。12426416815064436381251250123456789101112若一组关键字为（若一组关键字为（26，36，41，38，44，15，68，12，06，51，25），散列函数定），散列函数定义为：义为：H(key)=key%13。用拉练法建立的散列表为：用拉练法建立的散列表为：125解决冲突的方法n拉链法q优点:n不会堆积,所以平均查找时间较短n动态申请空间,适用于造表前无法确定表长的情况n删除处理简单快速n链长易控制,一般较短126解决冲突的方法n负载系数的定义和作用q设key的数量为N,散列表的大小为M,则N/M称负载系数或装填因子(loadfactor),它表现了平均情况下每个链的长度q我们一般预先规定好这个值,然后当不够的时候再增加hash表的长度(re-hash),这样可以保证链的平均长度不超过负载系数127解决冲突的方法n增加时一般作两倍的增加，而且增加后需要将所有的表元素全部重新求值放置(因为m变了)n一般取值为0.75128解决冲突的方法n聚集(clustering)现象又称二次聚集,指处理冲突中发生的两个第一个hash地址不同的记录争夺同一个后继hash地址的情况,常发生在有大量key对应于同一Hash函数值的情况下n聚集现象仅出现于使用闭散列方法时n当使用线性探测法时特别容易发生聚集现象,很容易使散列查询退化为对于链表或者数组的顺序查询129解决冲突的方法n假设Hash函数为H(key)=key MOD 11,表中已经有key 17,60,29,此时分别占据6,7,5;然后再插入38n此时可以发现,当表中5,6,7都被占据后,凡是函数值为5,6,7,8的key都将争夺8这个位置!130例题n在初始为空的哈希表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN),哈希函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为0:6，采用线性再散列法处理冲突。插入后的哈希表应该如_B_所示。()A.0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B.0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C.0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D.0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON131例题n若待散列的序列为(18,25,63,50,42,32,9)，哈希函数为H(key)=key MOD 9，哈希表长度为9，与18发生冲突的元素有_个n答案：2132例题n已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的散列表，假设利用除余法构造散列函数。133例题答案1.为了减少冲突，通常令装填因子Apr-Aug2-Dec3-Feb5-Jan-Jun-Jul6-Mar-May7-Oct-Nov9-Sep137练习答案012345678910111213141516AprAugDecFebJanMarMayJunJulSepOctNov138范围查询n定义:q在指定集合中有多少记录的关键字是落在指定范围中n一维的情况:q记录可以看作直线上的点q问题可以看作有多少点落入指定线段区域中139课程安排n课程介绍n栈、队列和向量 n树n查找n排序n图140排序 n大纲描述：q排序基本概念；q插入排序，希尔排序，选择排序，快速排序，归并排序，基数排序等排序算法基本思想；q算法代码及基本的时间复杂度分析；q堆的定义，堆的生成。141排序基本概念n排序(Sorting)：q重排一个记录序列,使之成为按关键字有序q常见排序可分为以下五类：n插入排序（简单插入排序、希尔排序）n交换排序（冒泡排序、快速排序）n选择排序（简单选择排序、堆排序）n归并排序n计数排序（多关键字排序）142插入排序46 26 22 68 48 42 36 84 66 22*26 46 22 68 48 42 36 84 66 22*22 26 46 68 48 42 36 84 66 22*22 26 46 68 48 42 36 84 66 22*22 26 46 48 68 42 36 84 66 22*22 26 42 46 48 68 36 84 66 22*22 26 36 42 46 48 68 84 66 22*22 26 36 42 46 48 68 84 66 22*22 26 36 42 46 48 66 68 84 22*22 22*26 36 42 46 48 66 68 84143希尔排序n定义qShell Sortq又称“缩小增量排序”（Diminishing Increment Sort），也是一种属于插入排序类的算法，但时间效率较其他排序方法有较大改进q基本思想是：先将整个待排记录序列分割为若干子序列分别进行直接插入排序，待整个序列的记录“基本有序”时，再对全体记录进行一次直接插入排序144冒泡排序n交换排序的一种n依次比较相邻的两个待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”n每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置n直到全部元素有序为止/直到某次冒泡过程中没有发生交换为止145快速排序n就平均时间而言，快速排序是目前被认为最好的一种内部排序方法,由C.A.R.Hoare发明n分治法(divide and conquer)思想的体现nUnix系统函数库所提供的标准排序方法nC标准函数库中的排序方法直接就命名为qsort()146快速排序n基本思想:q是对冒泡排序的一种改进q选取一个轴值,然后根据此轴值通过一趟排序对记录集进行一次分割,然后对分割后产生的两个记录子集分别进行快速排序147快速排序n基本概念:q轴值(pivot):n书上称枢轴n用于将记录集分割为两个部分的那个键值q分割(partition):n将记录集分为两个部分,前面部分记录的键值都比轴值小,后面部分的键值都比轴值大148快速排序149快速排序4938659776132749 38659776132749273865977613 492738 97761365492738139776 6549273813 76976549273813 49 76 97 654949temp150例题n写出对于结点序列（46，26，22，68，48，42，36，84，66）进行第一次分割后序列的情况，注意列出步骤的每一步。151例题答案【】26，22，68，48，42，36，84，6636，26，22，68，48，42，【】，84，6636，26，22，【】，48，42，68，84，6636，26，22，42，48，【】，68，84，6636，26，22，42，【】，48，68，84，6636，26，22，42，46，48，68，84，66152练习n已知序列（2,8,7,1,3,5,6,4），如果选用4作为枢轴，那么进行一次分割后序列表现是怎样的？n答案：2，3，1，4，7，5，6，8153练习n对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是_。n答案：13，38，27，49，76，97，65，50154简简单单选选择择排排序序示示例例49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697155例题n对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是n答案：简单选择排序156练习n若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序列的状态是_。157练习答案n13，38，65，97，76，49，27，50n13，27，65，97，76，49，38，50n13，27，38，97，76，49，65，50158堆的定义，堆的生成n1964年威洛姆斯(J.willioms)提出堆排序n属于树型选择排序，仅需要一个记录大小的辅助空间，每个待排序记录仅占有一个存储空间。159堆的定义，堆的生成n定义：qn个元素的序列k1,k2,kn当且仅当满足下列关系时，称之为堆：nkik2i且kik2i+1或nkik2i且kik2i+1q等价的树的定义：n如果一棵完全二叉树,其中每个节点的键值不小于(或者不大于)其子树的所有节点的键值,则称这棵二叉树为(最大值/最小值)堆(max/min heap)160堆的定义，堆的生成10155625307010 15 56 25 30 70小根堆示例小根堆示例161堆的定义，堆的生成70563025151070 56 30 25 15 10大根堆示例大根堆示例162堆的定义，堆的生成n堆排序：q若在输出堆顶的最值之后，使得剩余n1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反腐执行，便能得到一个有序序列，这个过程称为堆排序。163堆的定义，堆的生成n堆排序基本思想:1.将记录集调整为堆2.输出堆顶的最值记录3.将剩下记录重新调整为一个堆4.重复2,3直至所有记录被输出n堆排序关键问题:q如何将一个记录集调整为堆?164堆的定义，堆的生成n堆生成/调整算法:q从树的最后一个非叶子节点开始,也就是从数组的第length/2-1个元素开始调整q每次比较当前节点和及其左右子节点,取三者中最大者作为根q按逆层次序考察,直至根节点,也就是数组的第一个元素165堆的定义，堆的生成n堆排序算法：q先将初始堆调整成一个最大值堆；q然后将最值与最后一个元素对调，将去除最后一个元素后剩余的堆重新调整为一个最大值堆；q继续以上过程直至最后一个元素。166919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8堆的定义，堆的生成167131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后堆的定义，堆的生成168（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591堆的定义，堆的生成169050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后堆的定义，堆的生成170（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891堆的定义，堆的生成171（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891堆的定义，堆的生成172（g g）重建的堆）重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891堆的定义，堆的生成173（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891堆的定义，堆的生成174（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891堆的定义，堆的生成175（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891堆的定义，堆的生成176（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891堆的定义，堆的生成177（l l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891堆的定义，堆的生成178（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891堆的定义，堆的生成179（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆的定义，堆的生成180练习n已知序列88，91，42，23，24，16，5，13，用堆排序方法进行排序，求排序过程中堆的状况。181练习答案n91，88，42，23，24，16，5，13n13，88，42，23，24，16，5，91n88，24，42，23，13，16，5，91n5，24，42，23，13，16，88，91n42，24，16，23，13，5，88，91n5，24，16，23，13，42，88，91n24，23，16，5，13，42，88，91n13，23，16，5，24，42，88，91182练习答案n23，13，16，5，24，42，88，91n5，13，16，23，24，42，88，91n16，13，5，23，24，42，88，91n5，13，16，23，24，42，88，91n13，5，16，23，24，42，88，91n5，13，16，23，24，42，88，91183练习n序列（4,1,10,14,16,9,3,2,8,7）是否是一个最大值堆？如果不是请将其调整为一个最大值堆，并且使用堆排序算法进行排序，写出过程中每步序列的变化状况。184归并排序nJon von Neumann于1945年提出n彻底的分治法,完全的等分(相对于快速排序而言)n适用于巨量数据的排序nJava类库所提供的标准排序方法n所谓归并是指将两个或两个以上有序表合并为一个有序表的过程185归并排序(25