第2章查找和排序(编辑修改稿)

第2章查找和排序(编辑修改稿)内容摘要：

r = H（ key） 建立哈希函数的原则 – 均匀性 H（ key） 的值均匀分布在哈希表中； – 简单 以提高地址计算的速度。 下一页 上一页 停止放映 [第 35页 /81] 冲突及冲突处理 在哈希元素求解过程中 ， 不同关键字值对应到同一个存储地址的现象称为冲突。 即关键字 K1  K2， 但哈希函数值 H（ K1）= H（ K2）。 均匀的哈希函数可以减少冲突 ， 但不能避免冲突。 发生冲突后 ， 必须解决；也即必须寻找下一个可用地址。 处理冲突是建立哈希表过程中不可缺少的一部分。 下一页 上一页 停止放映 [第 36页 /81] 处理冲突 —— 开放地址法 当发生地址冲突后 ， 求解下一个地址用 Hi =( H（ key） +di） MOD m i=1,2,… ,k(k  m1) 其中 : H(key)为哈希函数 ,m为哈希表长度 ,di为增量序列。 增量序列的不同取法 ， 又构成不同的开放地址法。 线性探测再散列 di=1,2,… ,m1 二次探测再散列 di=12 , 12, 22, 22, … ,+k2, k2(k  m/2) 下一页 上一页 停止放映 [第 37页 /81] 处理冲突 —— 链地址法 当发生地址冲突后 ,将所有函数值相同的记录连成一个单链表。 下一页 上一页 停止放映 [第 38页 /81] 链地址法处理冲突 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈希表。 表长取 9,即 [0~8]。 哈希函数设定为 : H(key) = key MOD 8。 1 2 3 4 5 6 7 41 1 ^ 46 13 ^ 30 ^ 22 ^ 53 ^ ^ ^ 67 H(22)=H(46)=H(30)=6 H(53)=H(13)=5 H(67)=3 H(41)=H(1)=1 下一页 上一页 停止放映 [第 39页 /81] 哈希查找操作步骤 用给定的哈希函数构造哈希表 根据选择的冲突处理方法解决地址冲突 在哈希表的基础上执行哈希查找 下一页 上一页 停止放映 [第 40页 /81] 建立哈希表 建立哈希表操作步骤： step1 取数据元素的关键字 key， 计算其哈希函数值 （ 地址 ）。 若该地址对应的存储空间还没有被占用 ， 则将该元素存入；否则执行 step2解决冲突。 step2 根据选择的冲突处理方法 ， 计算关键字 key的下一个存储地址。 若下一个存储地址仍被占用 ， 则继续执行 step2， 直到找到能用的存储地址为止。 下一页 上一页 停止放映 [第 41页 /81] 举例 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈希表。 表长取 9,即 [0~8]。 哈希函数设定为 : H(key) = key MOD 8 ,用线性探测解决冲突 Hi=(H(key)+di) MOD m ,di=1,2,… ,m1。 0 1 2 3 4 5 6 7 8 22 22 0 1 2 3 4 5 6 7 8 41 比较次数： 1 1 取 41，计算 H（ 41） =1，该地址空，可用； 取 22，计算 H（ 22） =6，该地址空，可用； 下一页 上一页 停止放映 [第 42页 /81] 举例（续一） 取 53，计算 H（ 53） = 5，该地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比较次数： 1 1 1 22 41 53 46 0 1 2 3 4 5 6 7 8 比较次数： 1 1 1 2 取 46，计算 H（ 46） = 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，该地址空，可用； 下一页 上一页 停止放映 [第 43页 /81] 举例（续二） 取 30，计算 H（ 30） = 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，该地址冲突，再用线性探测法计算下一个可用地址； Hi=0，地址空，可用； 22 41 0 1 2 3 4 5 6 7 8 53 比较次数： 3 1 1 1 2 46 30 22 41 53 46 0 1 2 3 4 5 6 7 8 比较次数： 3 1 6 1 1 2 30 13 取 13，计算 H（ 13） = 5，依法解决冲突，得出： 下一页 上一页 停止放映 [第 44页 /81] 举例（续三） 取 1，计算 H（ 1） = 1，该地址冲突，解决冲突可得： 22 41 0 1 2 3 4 5 6 7 8 53 46 30 13 比较次数： 3 1 6 3 1 1 2 1 22 41 53 46 30 13 1 67 比较次数： 3 1 6 3 2 1 1 2 0 1 2 3 4 5 6 7 8 取 67，计算 H（ 67） = 3，冲突，解决冲突，得出： 下一页 上一页 停止放映 [第 45页 /81] 哈希查找 哈希查找的过程和建立哈希表的过程是一致的。 设哈希表为 HST[0~M1]， 哈希函数取 H（ key） ，解决冲突的方法为 R（ x） ， 则哈希查找步骤为： Step1 对给定 k值 ， 计算哈希地址 Di=H（ k） ；若 HST[i]为空 ， 则查找失败；若 HST[i]=k， 则查找成功；否则 ， 执行 step2（ 处理冲突 ）。 Step2 重复计算处理冲突的下一个存储地址 Dk=R （ Dk1 ） ， 直到 HST[Dk] 为空 ， 或HST[Dk}=k为止。 若 HST[Dk]=K， 则查找成功 ，否则查找失败。 下一页 上一页 停止放映 [第 46页 /81] 查找举例 以上述哈希表为例。 哈希函数为 H(key)=key MOD 8, 设有数列 {22,41,53,46,30,13,1,67},用线性探测法解决冲突 ,建立的哈希的表为 : 0 1 2 3 4 5 6 7 8 比较次数： 3 1 6 3 2 1 1 2 22 41 53 46 30 13 1 67 8 1 8 19 平均查找长度 ASL= (3+1+6+3+2+1+1+2)= 查找 key = 67 比较 两次找到 ,查找成功。 查找 key = 21 比较 8次找不到 ,查找失败。 示例 下一页 上一页 停止放映 [第 47页 /81] 排序基本概念 排序是计算机内经常进行的一种操作 ， 其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。 例如将学生记录按学号排序 ，将课程记录按课程编码排序。 排序的形式化定义为：假设含 n个记录的序列为 { R1, R2,… ， Rn }， 其相应的关键字序列为{ K1, K2,… ， Kn }。 这些关键字相互之间可以进行比较 ， 即在它们之间存在着这样一个关系Kp1≤K p2≤ … ≤K pn， 按此固有关系将最初的记录序列重新排列为 { Rp1, Rp2, … ， Rpn }的操作称作排序。 下一页 上一页 停止放映 [第 48页 /81] 排序分为 内部排序 和 外部排序。 若整个排序过程不需要访问外存便能完成，则称此类排序问题为 内部排序 ； 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为 外部排序。 本节只讨论内部排序的若干方法 下一页 上一页 停止放映 [第 49页 /81] 内部排序分类方法 • 按方法实现特点可分为 插入排序、选择排序、交换排序、归并排序 等等； • 按方法效率可分为简单的排序法、先进的排序法等等。 简单的排序法 包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为 O(n2)。 而 先进的排序法 包括 快速排序、归并排序等， 它们的 时间复杂度 大约 为 O(nlog2n)。 下一页 上一页 停止放映 [第 50页 /81] 插入排序算法 • 基本思想： 将 n个元素的数列分为已有序和无序两个部分。 {{a1}， {a2， a3， a4， … ,an}} {{a1(1)， a2(1)}， {a3(1)， a4(1) … ,an(1)}} … ... {{a1(n1)， a2(n1) ， … }, {an(n1)}} 有序 无序 •每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较 ,找出插入位置 ,将该元素插入到有序数列的合适位置中。 下一页 上一页 停止放映 [第 51页 /81] 插入排序算法步骤 • Step1 从有序数列 {a1}和无序数列 {a2,a3,… ,an}开始进行排序。 • S。