1、查找与排序,专题三,数据结构与控制算法分析,学习内容与要求,学习和掌握顺序查找和折半查找算法的原理和实现；学习和掌握二叉排序树的概念及其构造方法、二叉排序树的查找算法原理。学习和掌握选择排序、交换排序、插入排序、归并排序和快速排序方法的原理。,第 2 页,1 Search(查找/搜索),第 3 页,第 4 页,所谓查找（或搜索），就是在数据集合中寻找满足某种条件的数据对象: 1.查找成功 即找到满足条件的数据对象时, 作为结果, 可报告该对象在结构中的位置, 还可给出该对象中的具体信息。 2.查找不成功 或搜索失败。作为结果, 应报告一些信息, 如失败标志、位置等 。,通常称用于查找的数据集合
2、为查找结构，它是由同一数据类型的数据(或记录)组成。每个对象有若干属性，其中有一个属性，其值可唯一地标识这个对象，称为关键字。使用基于关键字的搜索，查找结果应是唯一的。但在实际应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一。,第 5 页,实施查找时有两种不同的环境静态环境 查找结构不需进行插入和删除操作。 静态查找表,第 6 页,动态环境 查找过程中可能要对查找结构执行数据插入、删除或修改等操作，并对查找结构进行调整，结构可能发生变化。 动态查找表动态查找表的表结构是在查找过程中动态生成的。,第 7 页,以线性结构表示静态查找表。基本原理：将待查找记录依次逐个与表
3、中记录进行比较。,1.1 顺序查找（Sequential Search),第 8 页,SL.elem,顺序查找过程（从前向后查找）,假设给定查找值 e=64,要求 SL.elemk = e, 问: k = ?,k,k,第 9 页,SL.elem,i,SL.elem,i,60,i,key=64,key=60,i,64,顺序查找过程（从后向前查找）,0单元用于存放待查找关键字，作为“哨兵”(guard),返回0,返回7,第 10 页,int Search_Seq( TB SL, TYPE key ) SL.elem0.key = key; / “哨兵” for (i=SL.length; SL.e
4、lemi.key!=key; -i); / 从后往前找 return i; / 查找成功时i为有效下标,否则i为0,顺序查找算法实现（从后向前查找）,第 11 页,查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数,查找算法的评价指标,第 12 页,查找算法的平均查找长度ASL(Average Search Length) 指为了确定记录在查找表中的位置，需要和给定值进行关键字比较的次数的期望值:,其中，n为表长，Pi为查找表中第i个记录的概率，且 ；Ci为查找到该记录时，曾和给定值进行关键字比较的次数。,第 13 页,在等概率情形，查找任一
5、记录的概率相等：pi = 1/n, i = 1, 2, , n,查找不成功时，,查找成功时，,以从前向后顺序查找算法为例，,查找算法时间复杂度？,O(n),顺序查找算法总结查找长度： 查找成功:最少比较次数 1 最多比较次数 n 平均比较次数 (n+1)/2 查找失败:最少比较次数 n 最多比较次数 n 平均比较次数 n优点：查找结构无特殊要求（线性结构均适用）；算法简单；缺点：查找效率较低，不适于大表查找。,第 14 页,第 15 页,上述按顺序查找表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找结构。,1.2 折半查找（二分查找）（Binary Search),若静态查找表为有
6、序表，则查找过程可以基于“折半”进行。,基于有序顺序表的折半查找,设n个数据对象存放在一个有序顺序表中，并按其关键字值从小到大（或从大到小）排好序。原理：折半查找时, 每次都先求出位于查找区间正中的对象的下标mid，用其关键字与给定值x比较，然后根据比较结果将查找区间缩小一半，直至找到被查找对象。,第 16 页,折半查找算法（设数据按关键字从小到大有序排列）,1.Elementmid.key=x 查找成功；2.Elementmid.keyx 把查找区间缩小为表的前半部分，继续折半查找；3.Elementmid.keyKey,因此, high=mid-1=4. 由于此时highlchild=B-
7、rchild B-rchild=A,最低层失衡结点为A，在结点A的左子树的右子树上插入新结点S后，导致失衡，假设在CL下插入S，由A、B、C的平衡因子可知，CL与CR深度相同，BL与AR深度相同，且BL、AR的深度比CL、CR的深度大1；为恢复平衡并保持二叉排序树的特性，可将B改为C的左子，而C原来的左子CL改为B的右子，然后将A改为C的右子，C原来的右子CR改为A的左子；这相当于以B为轴，对A做了一次顺时针旋转。,不平衡二叉排序树的调整LR型,不平衡二叉排序树的调整LR型,A,B,C,C,A,B,A-lchild=c-rchild B-rchild=c-lchildc-rchild=Ac-l
8、child=B,最低层失衡结点为A，在结点A的右子树的右子树上插入新结点S后，导致失衡，由A和B的平衡因子可知，BL、BR和AL深度相同，为恢复平衡并保持二叉排序树的特性，可将A改为B的左子，B原来的左子BL改为A的右子，这相当于以B为轴，对A做了一次逆时针旋转。,不平衡二叉排序树的调整RR型,不平衡二叉排序树的调整RR型,A-rchild=B-lchild B-lchild=A,最低层失衡结点为A，在结点A的右子树的左子树上插入新结点S后，导致失衡，假设在CR下插入S，由A、B、C的平衡因子可知，CL与CR深度相同，AL与BR深度相同，且AL、BR的深度比CL、CR的深度大1；为恢复平衡并保
9、持二叉排序树的特性，可将B改为C的右子，而C原来的右子CR改为B的左子，然后将A改为C的左子，C原来的左子CL改为A的右子；这相当于以B为轴，对A做了一次顺时针旋转。,不平衡二叉排序树的调整RL型,不平衡二叉排序树的调整RL型,A,B,C,A-rchild=c-lchild B-lchild=c-rchildc-lchild=Ac-rchild=B,1、引入大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。在 1970 年由 R bayer 和 E macreight 提出用B
10、_ 树作为索引组织文件。提高访问速度、减少时间。,内存,用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,B_ 树,m 阶 B_ 树的 定义,定义：一棵m阶的B-树，或者为空树，或为满足下列特性的m叉树： 树中每个结点至多有m棵子树； 若根结点不是叶子结点，则至少有两棵子树； 除根结点之外的所有非终端结点至少有m/2 棵子树； 所有的非终端结
11、点中包含以下信息数据：（n，A0，K1，A1，K2，Kn，An）其中：Ki（i=1,2,n）为关键码，且KiKi+1，Ai为指向子树根结点的指针(i=0,1,n)，且指针Ai-1所指子树中所有结点的关键码均小于Ki (i=1,2,n)，An所指子树中所有结点的关键码均大于Kn， m/2 1nm 1 ，n为关键码的个数。 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。,例如：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数至少为 m/2 = 2 个；结点的关键字个数至少为 1 。该 B_ 树
12、的深度为 4。叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 层,第 2 层,第 3 层(L层),第 4 层(L1层),一棵5阶的B-树，其深度为4,B树(续),B树的查找 1、首先找到根结点,与根结点各键值进行比较，如果 KxKi+1则查找Pi+1指向的结点；如果Ki KxKi+1则查找Pi指向的结点。 2、如果顺着某个指针往下找时遇到树叶，则说明Kx不在B树中，即查找失败。 3、在下一个结点查找时，重复1,B树(续),在往m阶B树中插入一个关键字（key）时，不是在树中添加一个树叶，而是首先在最底层的某个
13、非终端结点中添加一个关键字，若插入后该结点的关键字数目不超过m-1,则插入完毕；否则要进行分裂结点操作，并且这个分裂过程可能会一直波及到根结点。设某个结点已有m-1个关键字，那么，在插入一个关键字后，该结点将分裂成两个结点：左边一个结点包含前 个关键字，右边一个结点包含后m-m/2个关键字，而第m/2个关键字被插入到上一级（双亲）结点中。,B树的插入,阶为7的B树一般来说,要把一个新项目插入到阶为m的B树中处,当所有叶都在l级上,则把新的键插入到l-1,如果该结点现在含有m个键,则把它分为两个结点,并且把键K m/2插入到原来结点的父亲处(于是,父亲处结点的指针p为序列P, K m/2,P所替
14、代).如果需要分裂根结点,根结点是没有父亲的,则只需建立包含单个键K m/2的一个新根结点和两个指针,这样树就长高了一级.,B树(续),B树的删除1、如果要删除的关键字不在最下面一层的非终端结点中，则可先把待删关键字与它在B树中的后继对换位置，然后删除关键字2、如果要删除的关键字在最下面一层的非终端结点中，则把它从所在的结点中删除时，可能会导致此结点中关键字少于 (即它的孩子结点少于m/2个)因此，需要进行结点的合并操作。结点的合并操作可以根据以下两种情况分别进行。,(1)若被删出关键字所在结点中正好有 个关键字而与该结点相邻的左兄弟（或右兄弟）结点中的关键字多于 个则可将其兄弟结点中最大（或
15、最小）的关键字移到双亲结点中，而将双亲结点中该上移关键字的后面一个（或前面一个）关键字下移到被删除关键字所在的结点中。(2)若被删除关键字所在的结点和其相邻的兄弟结点中的关键字都是 个，则可将删除了关键字的结点和它的双亲结点的一个关键字合并到它的兄弟结点中。如果因此使双亲结点中的关键字少于 个，则需要继续进行合并。,1.4 哈希表技术,以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零。,65,问题：对
16、于频繁使用的查找，我们希望平均查找长度ASL接近于0,预先知道所查关键字在表中的位置记录在表中位置和其关键字之间存在一种确定的关系,只有一个办法,66,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。若以下标为000 999 的顺序表表示学号查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,67,哈希查找的基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法哈希函数：在记录的关键字与记录在表中的存储位置之间
17、建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。哈希地址：由哈希函数求出的记录存储位置称为哈希地址，表示成：addr(ai)=f(ki)ai是表中的一个元素(记录)addr(ai)是ai的存储地址ki是ai的关键字,68,哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表，也叫散列表。哈希查找：又叫散列查找，利用哈希函数进行查找的过程叫,69,Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai,例：对于如下 9 个关键字,Chen,Zhao
18、,Qian,Sun,Li,Wu,Han,Ye,Dai,问题: 若添加关键字 Zhou , 怎么办？,能否找到另一个哈希函数？,设 哈希函数 f(key) = (ASC(关键字第一个字母) -ASC(A)+1)/2,70,哈希函数是一个映象，即 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可；由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1 key2，而 f(key1) = f(key2)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。在构造哈希表时，除了需要选择一个
19、“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种处理冲突 的方法。,71,构造哈希函数的几种方法,对数字的关键字可有下列构造方法,若是非数字关键字，则需先对其进行数字化处理,1. 直接定址法,3. 平方取中法,5. 除留余数法,4. 折叠法,6. 随机数法,2. 数字分析法,72,(1) 直接定址法,构造：取关键字或关键字的某个线性函数作哈希函数 H(key) = key 或者 H(key) = a. key + b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少,73,(2) 数字分析法,构造：对关键字进行分析，取关键字的若干位或其组合作哈
20、希地址特点：适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,74,(3) 平方取中法,构造：以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。特点：关键字中的每一位都有某些数字重复出现频度很高的现象。,75,(4) 折叠法,构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加特点：适于关键字位数很多，且每一位上数字分布大致均匀情况,76,例 关键字为 ：0442205864
21、，哈希地址位数为4,77,(5) 除留余数法,构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即 H(key)=key % p p=m 且P 一般应为接近 m 的素数或是不含20 以下的质因子特点简单、常用: 可与上述几种方法结合使用p的选取很重要: p选的不好，容易产生同义词,对P要加一定的限制,78,给定一组关键字为：12, 39, 18, 24, 33, 21 假定hash表的长度为12若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3,例如：,为什么要对 p 加限制？,若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的
22、倍数”的地址上，从而增加了“冲突”的可能。,79,(6) 随机数法,构造：取关键字的随机函数值作哈希地址H(key)=random(key)适于关键字长度不等的情况,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,80,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数, ,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址,81,处理冲突的方法,处理冲突 ：为产生冲突的地址寻找下一个哈希地址。主要有二种方法开放定址法链地址法
23、,82,思想：为产生冲突的关键字寻找一个新的地址 Hi(key)， 求得一个地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) H1 = (H(key) + d1 ) % m H2 = (H(key) + d2 ) % m Hi = ( H(key) + di ) % m i=1, 2, , s,(1) 开放定址法,83,对增量 di 有三种取法线性探测再散列：di=1,2,3,m-1二次探测再散列：di=1,-1,2,-2,3,k伪随机探测再散列：di=伪随机数序列注意：增量 di 应具有“完备性”,即：产生的 Hi 均不相同，且所产生的 s个 Hi 值
24、能覆盖哈希表中所有地址。要求： 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, 等）；随机探测时的 m 和 di 没有公因子。,84,例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key % 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中,(1) H(38)=38 % 11=5 冲突 H1=(5+1) % 11=6 冲突 H2=(5+2) % 11=7 冲突 H3=(5+3) % 11=8 不冲突,38,(2) H(38)=38 % 11=5 冲突 H1=(5+1) % 11=6 冲突 H2=(5
25、-1) % 11=4 不冲突,38,(3) H(38)=38 % 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) % 11=3 不冲突,38,线性探测,二次探测,随机探测,将所有哈希地址相同的记录都链接在同一链表中 例：关键字集合 19, 01, 23, 14, 55, 68,11, 82, 36 哈希函数为： H(key)=key % 7,(2) 链地址法,0123456,14,01,36,19,82,23,11,68,55,86,哈希表的查找及其性能分析,查找过程：和造表过程一致，对于给定值，由哈希函数和解决冲突的方法定位记录的存储位置。,87,例：给出哈希表HT，哈希函数 H
26、(key)=key % 11,解决冲突方法：开放地址法中线性探测再散列Hi(key)=(H(KEY)+di)% 11 (d1=1, d2=2, d3=3, ),试查找关键字19 、02,查找关键字19,用哈希函数求19 对应的哈希地址：H(19)=19 % 11=8,将HT8与19比较相等查找成功,88,查找关键字02,用哈希函数求02 对应的哈希地址：H(02)=02 % 11=2,将HT2与02比较不相等,用解决冲突方法为02求下一个“地址” （取d1=1） H1 (02)=(H(02)+ d1)% 11=3,将HT3与02比较相等查找成功,89,查找算法实现：开放定址哈希表,int ha
27、shsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1,90,bool SearchHash (HashTable H, KeyType K, int &p, int &c) / 在开放定址哈希表H中查找关键码为K的记录 / SearchHash,p = Hash(K); / 求得哈希地址,whil
28、e (H.elemp.key != NULLKEY / 求得下一探查地址 p,if (K=H.elemp.key) return 1; / 查找成功，返回待查数据元素位置 p,else return 0; / 查找不成功,91,bool InsertHash (HashTable &H, Elemtype e) ,Int c = 0;,if ( HashSearch ( H, e.key, p, c ) = SUCCESS ) return DUPLICATE; / 表中已有与 e 有相同关键字的元素,else H.elemp = e; +H.count; return OK; / 查找不成功
29、时，返回 p为插入位置,else RecreateHashTable(H); / 重建哈希表,if ( c hashsizeH.sizeindex/2 ) / 冲突次数 c 未达到上限，（阀值 c 可调） ,92,哈希表查找分析从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。,决定哈希表查找的ASL的因素：(1) 选用的哈希函数； (2) 选用的处理冲突的方法； (3) 哈希表饱和的程度，装载因子 =n/m 值的大小（n记录数，m表的长度）,93,一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。
30、例: 关键字集合 7, 15, 20, 31, 48, 53,64, 76, 82, 99 ,线性探测处理冲突时， ASL =,平方探测处理冲突时，ASL =,链地址法处理冲突时， ASL =,2.4,2.0,1.7,94,线性探测再散列,链地址法,二次探测或随机探测再散列,可以证明：查找成功时有下列结果：,95,从以上结果可见：,哈希表的平均查找长度是 的函数，而不是 n 的函数。,这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内。, 这是哈希表所特有的特点。,2 Sort(排序),第 96 页,第 97 页,什么是排序？,排序是计算机内经常进行的
31、一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,第 98 页,一般情况下，假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn ,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rp3 的操作称作排序。,第 99 页,内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。,第 100 页,内部排序的方法,内部排序的过程是一个逐步扩大有序记录序列长度（同时也缩小无序序列长度）的过程。,
