VB教程03.查找和排序课件

1、查找查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的1 顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素： 1查

2、找第n-1个元素：2.查找第1个元素： n查找第i个元素： n+1-i查找失败： n+1顺序查找方法的ASL2 折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 2

3、1 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185110742936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法评价判定树：描述查找过程的

4、二叉树叫有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASL1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38分块查找方法评价ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，

5、这样构成的表叫哈希查找又叫散列查找，利用哈希函数进行查找的过程叫例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫同义词：具有相同函数值的两个关键字，叫该哈希函数的哈希

6、函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分

7、布大致均匀情况例 关键字为 ：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)

8、+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函数 m哈希表表长 di增量序链地址法例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 冲突38例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 1

9、2 14127796855198420231011链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针哈希查找过程及分析哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYN哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置1 插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录

10、看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序算法描述算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：2(n-1)若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n)空间复杂度：S(n)=O(1)折半插入排序排序过程：用折半查找方法确定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.

11、i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )算法描述算法评价比较的次数大大减少，全部元素比较次数仅为O(nlog2n)。虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2) 时间复杂度：T(n)=O(n)空间复杂度：S(n)=O(1)希尔排序(缩小增量法)排序过程：先取一个正整数d1

12、n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2r2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止初态：46 82 40 52 67 31 21 73i=1： 46 40 52 67 31 21 73 82i=2： 40 46 52 31 21 67 73 82i=3： 40 46 31 21 52 67 73 82i=4

13、： 40 31 21 46 52 67 73 82i=5： 31 21 40 46 52 67 73 82i=6： 21 31 40 46 52 67 73 82i=7： 21 31 40 46 52 67 73 82算法描述算法评价时间复杂度最好情况（正序）比较次数：n-1移动次数：0最坏情况（逆序）比较次数：移动次数：空间复杂度：S(n)=O(1)T(n)=O(n)快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设

14、枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止例初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij49

15、65ji1349ij4997ij3 选择排序简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65