软件技术基础第三章

大学生软件技术基础，比较详细的

查找与排序技术

• 3.1基本的查找技术
  • 查找：给定的数据结构中查找指定的元素
  • 平均查找长度：与关键字进行比较的平均次数
    • ASL=pi*ci求和 i=｛1～n｝
      • pi为查找表中第i个数据元素的概率
      • ci为查找第i个数据元素时需比较的次数
  • 主要查找算法
    • 顺序查找
      • 性质
        • 思想：从第一个元素到最后一个元素逐个进行比较
        • 特点：最简单、最普通的查找方法
        • 适用范围：顺序与链式存储结构
      • 操作步骤
        • step1：从第一个元素开始查找
        • step2：用待查找关键字与各个节点关键字逐个进行比较；若找到相等节点，则查找成功；否则失败。
      • 算法评价
        • ASL=n\1*2\n（n+1）=2\（n+1）=O（n）
        • 一般情况下ASL=<2\n
        • 优点
          • 对结点的逻辑次序和存储结构无要求
          • N值较小时比较合适
        • 缺点
          • ASL较长
        • 讨论
          • 减少比较次数以提高效率（二分法）
    • 对分（折半）查找
      • 性质
        • 思想：有序序列中点设置为比较对象，如查找值小于中点，则将序列缩小到左半部分
        • 特点：高效的查找方法：明显减少比较次数，提高查找效率
        • 先决条件：表中数据元素必须有序
      • 操作步骤
        • step1：首先确定查找区间的中间位置
          • mid=int（（left+right）/2）
        • step2：用待查找关键字值与中间位置的关键字值进行比较
          • 相等：成功
          • 大于：后半部分继续二分查找
          • 小于：前半部分继续进行二分查找
        • step3：对确定的缩小区域再按二分公式，重复上述步骤
      • 算法评价
        • 数据结构
          • 一维数组
        • 优点
          • ASL<=log2n；一次比较后查找范围缩小一半
        • 缺点
          • 要求有序，所有数据元素要按大小排序
          • 顺序存储结构插入、删除操作不大便利
    • 分块查找
      • 性质
        • 顺序查找的一种改进方法
        • 用于分块有序表进行查找
      • 操作步骤
        • step1：先选取各块中最大关键字构成一个索引表
        • step2：对索引表进行对分或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找
      • 算法评价
        • 索引表使用对分法：ASL<=log2（s/n+1）+2/s
          • n为表长
          • s为块长
        • 优点
          • 插入删除操作方便
          • 只要找到相应的块，在块中任意位置操作均可
        • 缺点
          • 索引表增加了辅助存储空间
• 3.2哈希（hash）表技术（散列查找）
  • 性质
    • 通过计算存储地址的方法进行查找
    • 直接查找技术
      • 设表长为n。如存在一个函数i=i（k）（关键字j的映像函数），对表中的任意一个元素的关键字k，满足下列条件：
        • i=1～n
        • 对任意元素的关键字k1≠k2，恒存在i（k1）≠i（k2）
    • hash表
      • 设表长为n。如存在一个函数i=i（k）（关键字j的映像函数），对表中的任意一个元素的关键字k满足：i=1～n
    • 关键
      • 构造合适的hash码
      • 元素发生冲突时 要进行适当的处理
    • 原则
      • 均匀性：i（key）的值均匀分布在哈希表中
      • 简单：以提高地址计算的速度
  • 常用的构造方法
    • 截段法
      • 截取关键字中的一段
    • 分段叠加法
      • 各个编码串进行叠加再截段
    • 除法（求模取余法）
      • 将关键字编码除以表的长度得到的余数作为hash码
    • 乘法
      • 关键字编码与一个常数相乘后再除以表的长度求其余数作为hash码
  • 冲突以及冲突处理
    • 不同的关键字对应到同一个存储地址的现象称为冲突：k1≠k2，H（k1）=H（k2）
    • 发生冲突后必须解决（寻找下一个可用地址）
      • 开放地址法
        • Hi=（H（key）+di）
          • 线性探测再散列：di=1，2，3……k-1
          • 随机再散列：di=RN（i）
      • 链地址法
        • 发生地址冲突以后，将所有函数值相同的记录连成一个单链表
  • 操作步骤
    • 用给定的hash函数构造hash表
      • step1：取数据元素的关键字key，，计算其hash函数值（地址）。如对应的存储空间未被占用，则将该元素存入；否则执行step2解决冲突
    • 根据选择的冲突处理方法解决地址冲突
      • step2：根据选择的冲突处理方法，计算关键字的下一个存储地址。若下一个存储地址依然被占用，则继续执行step2
    • 在hash表的基础上执行hash查找
  • 哈希查找
    • 设哈希表为HSL【0～M-1】，哈希函数取H（key），解决冲突的方法为R（x）
      • step1：对给定k值，计算哈希地址为di=H（k）；若HSL【i】为空，则查找失败；若HSL【i】=k，则查找成功；否则执行step2
      • step2：重复计算处理冲突的下一个存储地址dk=R（dk-1），直到HSL【dk】为空，或HSL【dk】=k为止。若HSL【dk】=k，则查找成功，否则查找失败
    • 平均查找次数：（a=m/n（hash表填满率），n为hash表长度，m为关键字个数）
      • 线性hash表（2-a）/（2-2a）
      • 随机hash表 1/a ln（1-a）
• 3.3基本的排序技术
  • 性质
    • 定义：将记录按关键字递增或递减的次序排列起来
    • 描述：设n个记录的序列为｛R1，R2，R3……Rn｝，其相应关键字序列为｛K1，K2，K3……Kn｝，确定一种使关键字升序或降序的排序｛P1，P2，P3……Pn｝
  • 冒泡排序
    • 性质：两两比较待排序记录的关键字；并交换不满足顺序要求的偶对元素，直到全部满足
    • 算法步骤
      • step1：通过比较和交换将最大的一个关键字交换到最后
      • step2：如法炮制，后一趟冒泡
      • step3：最多执行n-1趟冒泡
    • 算法改进
      • 若某次冒泡中没有进行交换，说明序列已经有序，则停止交换
    • 算法评价
      • 如有序，只需进行一趟；无序则需进行n-1趟
      • 待排序序列基本有序适合这种算法
      • 这一算法是稳定的
  • 快速排序
    • 性质：
      • 对冒泡排序的改进，基于交换排序
      • 基本思想：先以某种方法选一个元素K为分界点，用交换的方法将序列分为两个部分———比该值小的放左边，大的放右边，在分别对左、右两部分实施上述分解过程，直到各子序列长度为一
        • K的选取方法
          • 左边第一个元素
          • 取中点
          • 最大和最小值的平均值
    • 算法步骤
      • step1：分别从两端开始，指针i指向第一个元素A【left】，指针j指向最后一个元素A【right】，分界点取K
      • step2：循环（i≤j） 左边：若K＞A【i】，则i=i+1，继续比较；若K≤A【i】，则将A【i】交换到右边。右边同上。当i=j时，一次分解操作完成
      • step3：在对分解出的左右两个子序列按上述步骤继续进行分解，直至不可再分（子序列长度为一）
    • 算法评价
      • 分界点选取不同，排序效果差距很大
      • 比较次数为nlogn
      • 这是一种不稳定算法
  • 简单插入排序
    • 基本思想：将n个元素的数列分为有序和无序，后将无序数列的第一个元素与有序数列从前往后逐个进行比较，插入有序数列合适位置
    • 算法步骤
      • step1：从有序数列｛a1｝无序数列｛a2，a3，a4……an｝开始进行排序
      • step2：处理第i个元素时，数列｛a1，a2，a3…ai-1｝已有序，数列｛ai……an｝无序。用ai于ai-1，ai-2进行比较，插入合适位置。（从前往后也可）
      • step3：重复step2，共进行n-1次的插入处理，数列全部有序
    • 算法评价
      • 插入算法比较次数和交换次数约为n^2/2
      • 这是一种稳定的算法
  • 希尔排序
    • 思想：采用插入法，将无序序列分为若干小的子序列，分别进行插入排序。按一定间隔抽取分为子序列。间隔d按给定公式减少：di+1=（di+1）/2，直至d等于1
    • 算法步骤
      • step1：将总长为n个元素的数列分为m个子序列，子序列内每个元素间距为d
      • step2：在第i+1步，两元素比较的间距取di+1=（di+1）/2。子序列中使用简单插入排序
      • step3：重复上述步骤，直到dk=1
    • 算法评价
      • 排序算法比较次数n^1.5
      • 这是一种不稳定的算法
  • 简单选择排序
    • 基本思想：每次从待排序记录中选出关键字最小或最大的放到已有序序列中最后或最前，直到全部有序
    • 算法步骤
      • step1：从原始数列｛a1，a2，a3……an｝开始进行排序，比较n-1次，从中选出最小关键字，放在有序数列中，形成｛a1｝，｛a2，a3……an｝，完成第一趟
      • step2：处理第i趟时，从剩下的n-i+1个元素中找出最小关键字，放在有序数列的后面
      • step3：重复step2，共进行n-1趟选择处理
    • 算法评价
      • 比较次数O（n^2）
      • 这是一种不稳定算法
  • 堆排序
    • 性质
      • 树型选择排序
      • 在排序中，将R【0】到R【n-1】看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点内在关系来选择关键字最小记录
      • 堆：n个关键字序列K1，K2，K3…Kn。Ki≤k2i和Ki≤K2i+1（父结点小于子结点）
    • 建堆
      • 只有一个结点的树和完全二叉树（所有序号i≥low（n/2）的结点都是叶子）中以这些结点为根的子树都是堆
      • 依次将序号为low（n/2） low（n/2）-1……1的结点作为根的子树都调整成堆
      • 筛选法
        • 如果R【i】的左右子树已是堆，这两个子树的根分别是各自子树中关键字最大的结点
        • 若根的关键字已是三者（根，左孩子，右孩子）中的最大者，则无需做任何调整；否则必须将具有最大关键字的孩子与根交换
        • 交换之后有可能导致新子树不再是堆，需要将新子树调整为堆。如此逐层递推，直到调整到树叶
    • 堆排序算法
    • 评价
      • 时间复杂度O（nlog2n）
      • 空间复杂性O（1）
      • 这是一种不稳定的排序方法