排序 排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序.ppt

《排序 排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序.ppt》由会员分享，可在线阅读，更多相关《排序 排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序 排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望排序算法选择v待排序的个数v记录本身的大小v关键字的分布v排序稳定性的要求第8章 查找searching查找 v也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素v关键字,是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价v查找速度v占用存储空

2、间多少v算法本身复杂程度v平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需将关键字和给定值进行比较的平均次数主要方法v顺序查找v二分查找v分块查找v哈希查找顺序查找v查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较v顺序查找方法的ASL二分查找v查找过程：每次将待查记录所在区间缩小一半v适用条件：采用顺序存储结构的有序表v算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较v若k=rmid.key，查

3、找成功v若krmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败vintbinsrch(JDr,int n,intk)int low,high,mid;low=1;high=n;while(lowrmid.key)low=mid+1;else high=mid-1;return(-1);算法评价v判定树：描述查找过程的二叉树v有n个结点的判定树的深度为log2n+1v折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度v折半查找的ASL分块查找v查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找v适用条件：分块有序表v算法实现用

4、数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针算法描述查找方法比较哈希查找v基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法v哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)vai是表中的一个元素vaddr(ai)是ai的存储地址vki是ai的关键字v哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址v哈希查找又叫散列查找，

5、利用哈希函数进行查找的过程v哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可v冲突：key1key2，但H(key1)=H(key2)的现象叫v同义词：具有相同函数值的两个关键字，叫该哈希函数的v哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法v直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或H(key)=akey+b特点v直接定址法所得地址集合与关键字集合大小相等，不会发生冲突v实际中能用这种哈希函数的情况很少v数字分析法构造：对关键

6、字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况v平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数则更难。一组关键字(0100,0110,1010,1001,0111)就无法使用数字选择法得到较均匀的散列函数。此时可采用平方取中法，即先通过求关键字的平方值扩大差别，然后再取中间的几位或其组合作为散列地址。例如，上述一组关键字的平方结果是：(0010000,0012100,1020100,1002001,0012321)若表长为1000，则可取中间

7、三位作为散列地址集。v折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类v移位叠加：将分割后的几部分低位对齐相加v间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况v关键字key=58242324169,哈希地址位数为3移位叠加 间界叠加582 582423 324241 241+69+961315 1243vH(key)=315 H(key)=243v除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm一般选P为小于或等于散列表长度m的某个

8、最大素数比较好。例如：m=8,16,32,64,128,256,512,1024P=7,13,31,61,127,251,503,1019特点v简单、常用，可与上述几种方法结合使用vp的选取很重要；p选的不好，容易产生同义词v随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况v选取哈希函数，考虑以下因素：计算哈希函数所需时间v关键字长度v哈希表长度（哈希地址范围）v关键字分布情况v记录的查找频率处理冲突的方法v若某个散列函数H 对于不相等的关键字key1和key2得到相同的散列地址(即H(key1)=H(key2)，则将该现象称为冲突。

9、v而发生冲突的这两个关键字则称为该散列函数H的同义词。v处理冲突的方法基本上可分为两大类：开放地址法、拉链法(链地址法)开放定址法v方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MODm，i=1,2,k(km-1)其中：H(key)哈希函数m哈希表表长di增量序列v 分类线性探测再散列：di=1,2,3,m-1二次探测再散列：di=1,-1,2,-2,3,k(km/2)伪随机探测再散列：di=伪随机数序列v表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key M

10、OD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中v链地址法v方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针v拉链法解决冲突的方法是：把具有相同散列地址的关键字值放在同一个单链表中，这个单链表称为同义词链表。若选定的散列函数的值域为0m-1，则可将散列表定义为一个有m个头指针组成的指针数组HTPm，凡是散列地址为i的结点，均插入到以HTPi，为头指针的单链表中。v已知一组关键字(26,36,41,38,44,15,68,12,06,51,25)，散列函数为H(key)%13，用拉链法解决冲突构造这组关键字的散列表。v哈希查找过程仍是一个给定值与关键字进行比较的过程v评价哈希查找效率仍要用ASLv哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度