计算机软件技术基础3-4 数据结构及算法(查找与排序).ppt

1 常用数据结构及其运算 第三章 2 3 1概述 3 2线性表 3 3栈与队 3 4树与二叉树 3 5图 3 6查找与排序 目录 3 3 6 1查找的基本概念3 6 2静态查找技术3 6 3动态查找技术3 4 4排序基本概念3 4 5简单选择排序3 4 6插入排序3 4 7交换排序 3 6查找与排序 4 2 查找表由同一类数据构成的用于查找的集合被称作查找表 查找表是具有一定存储结构的数据集合 比如顺序表结构 链式结构 树形结构等 3 关键字查找往往根据数据元素的某个属性进行 例如根据学号查找某个学生记录 这种被用于查找的元素属性一般称为关键字 它往往可以唯一标识一个元素 3 6 1查找的基本概念 1 什么是查找确定给定值k在含有n个记录的文件中的位置的过程称为查找 5 4 静态查找表查找表一旦建立 在以后的查找过程中就不会改变 它所对应的查找算法属于静态查找技术 5 动态查找表 查找表建立后 在后来的查找过程中仍会改变查找表的内容 它所对应的查找算法属于动态查找技术 动态查找的例子 词汇统计问题 就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数 解决方法是先建立一个空的查找表 以后每读到一个词就在查找表中查询一下 如果该词汇存在则将其使用次数加一 否则将新词插入到查找表中并设使用次数为一次 显然 这个查找表是不断扩张的 3 6 1查找的基本概念 6 6 平均查找长度 为了确定数据元素在查找表中的位置 需要将给定值和表中的数据元素的关键字进行比较的次数的期望值 平均查找长度ASL的计算方法为 n为表长 Pi为查找第i个元素的概率 Ci为找到该记录时 曾和给定值比较过的数据元素的个数 在等概率条件下 Pi 1 n 这时平均查找长度为 其中 3 6 1查找的基本概念 7 假设静态顺序查找表的存储结构为 structSSTable ElemType data 存储空间地址intlength 表的长度 顺序查找表的元素存放在data 0 至data length 1 中 3 6 2静态查找技术 8 1 顺序查找顺序查找的方法是从表的一端开始 逐一比较给定的数据key和表中数据元素的关键字x的值 若两个数据一致则查找成功 同时给出该数据元素在表中的位置 否则查找失败 3 6 2静态查找技术 9 顺序查找算法C 语言描述如下 intSqSearch SSTable 该算法若查找成功 则函数返回值为目标元素在表中的位置 否则返回0 这里元素位置从1开始算起 3 6 2静态查找技术 10 在上述算法中为了避免 出界 需在循环中作k L length的判断 这使算法的执行时间几乎增加一倍 为提高效率 对查找表的结构改动如下 适当设置数组长度 将元素存于data 1 至data length 1 中 在0号单元预存待查找数据key作为监视哨 改写查找过程为从后往前查找 因为循环查找过程至少会在0号单元停止 这样就不必在每一次循环中都判别是否数组出界 3 6 2静态查找技术 11 改进的顺序查找算法C 语言描述如下 intSqSearch SSTable 找不到时 k为0 该算法若查找成功 则函数返回值为目标元素在表中的位置 否则返回0 3 6 2静态查找技术 12 下面分析一下改进的顺序查找算法的时间性能 对于改进的顺序查找而言 找到第i个元素的比较次数Ci n i 1 所以在等概率查找的情况下 顺序表查找的平均查找长度为 3 6 2静态查找技术 13 2 折半查找 也称二分查找 顺序查找表的查找算法简单 但平均查找长度较大 如果顺序查找表的元素按照关键字的值有序存放 那么可利用高效的折半查找来完成查询 假定元素按关键字的值升序排列 折半查找的思路是将给定的数据与有序表中间位置的元素做比较 若两者相等则查找成功 若前者小于后者则在中间位置左边的元素中继续查找 若前者大于后者则在中间位置右边的元素中继续查找 不断重复这一过程直到查找成功 或者直到查找区间缩小为一个元素时却仍未找到目标 则查找失败 3 6 2静态查找技术 14 折半查找算法的步骤描述如下 设置查找区间初值 设下界low 0 设上界high length 1 若low high则计算中间位置mid low high 2 若keydata mid 则设low mid 1并继续执行步骤 若key data mid 则查找成功 返回目标元素位置mid 1 位置从1计数 若当low high时 key data mid 则查找失败 返回0 3 6 2静态查找技术 15 折半查找算法的C 语言描述如下 intBinSearch SSTable 不存在待查元素 3 6 2静态查找技术 16 对给定有序数列 5 6 11 17 21 23 28 30 32 40 进行半查找算法 查找关键字值为30的数据元素 则查找过程如下 第1次 5 6 11 17 21 23 28 30 32 40 low 0mid 0 9 2 4high 9第2次 5 6 11 17 21 23 28 30 32 40 low 5mid 7high 9 等概率情况下其平均查找长度为 即O log2n 3 6 2静态查找技术 17 将数据分成若干块 块与块间数据有序 块内数据无序1 算法思想 将各块中的最大关键字构成一个递增有序的索引表 先查找索引表 采用对分或顺序查找 以确定所在块 在所在块中进行顺序查找 3 分块查找 索引顺序查找 3 6 2静态查找技术 18 例 3 6 2静态查找技术 19 2 算法分析 平均查找长度 索引表平均查找长度 块表平均查找长度 其中 r 1 n 分为b块 每块中的记录数s n b 3 6 2静态查找技术 20 动态查找技术 动态查找技术所依赖的查找表以树状结构居多 例如二叉排序树 B 树 B 树等 它们的共同特点是结构灵活 易于实现插入 删除等操作 这里主要介绍简单易用的二叉排序树 3 6 3动态查找技术 21 二叉排序树的定义二叉排序树可能为一棵空的二叉树 若非空则必须满足以下特征 1 根结点左子树中所有结点的关键字小于根结点的关键字 2 根结点右子树中所有结点的关键字大于或等于根结点的关键字 3 根结点的左右子树也都是二叉排序树 一棵二叉排序树 3 6 3动态查找技术 22 建立了二叉排序树之后 若查找过程中不插入或删除元素 静态查找 则在二叉排序树中查找方法为 1 将给定数据key与根结点关键字x进行比较 若key x则查找成功 2 若keyx 则与右子树的根结点的关键字值进行比较 重复上述步骤 直到查找成功 或者一直比较到叶子结点也找不到目标元素 则查找失败 3 6 3动态查找技术 23 可定义二叉排序树结点如下 typedefstructBinNode ElemTypex 关键字structBinNode left right BinNodePtr 二叉排序树查找算法 静态查找 C 语言描述 BinNode search btree BinNodePtr 3 6 3动态查找技术 24 进行动态查找时 查找过程还涉及到插入新结点 其方法为 1 在二叉排序树中查找数据key 按前一页的方法 若查找成功则程序中止 若查找失败则转入下面插入过程 2 2 以数据key作为关键字建立新结点 假定查找过程最后到达某叶子结点 比较key与此叶子结点的关键字 若key小于后者则将新结点插入为叶子结点的左孩子 若key大于后者则新结点插入为叶子结点的右孩子 3 6 3动态查找技术 25 动态查找过程也是生成二叉排序树的过程 假定由整数序列 10 6 19 22 8 2 生成一棵二叉排序树 可以采用逐个元素插入的方法实现 1 首先将10作为根结点 2 然后插入6时 通过比较知6 10 所以将6作为10的左孩子插入 3 同理将19作为10的右孩子插入 4 整数22通过和10 19比较后 作为19的右孩子插入 5 依次插入剩余的其他元素 3 6 3动态查找技术 26 二叉排序树动态查找算法C 语言描述如下 BinNode Search Insert BinNodePtr 查找失败 插入新结点 见下一页 3 6 3动态查找技术 27 接上一页内容 if p NULL 建立新结点p newBinNode p left NULL p right NULL p x key 新结点不是根 则作为叶子插入if pre NULL if pre x p x pre left p 插入为左孩子elsepre right p 插入为右孩子 returnp 返回找到的结点或插入的新结点的指针 3 6 3动态查找技术 28 例 字符统计程序 该程序可统计由用户输入的一个字符串中各种字符的使用次数 程序算法是 首先建立空的二叉排序树 每次读入字符后就在树表中查询 若找到则将该字符使用次数加一 否则 将读入的字符插入二叉排序树 为记录字符使用次数 在二叉树结点定义中增加了使用次数属性 读完整个字符串后用中序遍历法读出每个字符使用次数 3 6 3动态查找技术 29 1 排序的定义就是把一组无序的记录按其关键字递增或递减的次序排列 便于数据的查找 2 稳定排序和不稳定排序对于 R1 R2 Rn 若有Ri Rj 在排序前Ri在Rj前 排序后Ri仍在Rj前 则称此排序方法是稳定的 反之为不稳定的 3 6 4排序基本概念 30 3 内部排序和外部排序内部排序 待排序记录存放在内存中进行排序 外部排序 待排序记录数量很大 在排序过程中需访问外存 4 基本操作1 对记录中关键字大小进行比较 2 将记录从一个位置移到另一个位置 3 6 4排序基本概念 31 选择排序是不断在待排序序列 无序区 中按记录关键字递增 或递减 次序选择记录 放入有序区中 逐渐扩大有序区 直到整个记录区为有序区为止 简单选择排序的基本思想是 将记录分为有序和无序两个序列 假定第k趟排序时 前面的R1 R2 Rk 1已经排好序 而后面的Rk Rk 1 Rn仍然无序 则选择Rk到Rn中的关键字最小的记录与Rk交换 交换后有序序列增加了第k个记录 当第n 1趟选择执行完 待排序记录只剩下1个 就不用再选了 在初始状态可以认为有序序列为空 1 方法 在当前无序序列中选择一个关键字最小的记录 并将它和最前端的记录交换 重复此过程 则逐渐形成由小 大的有序区 3 6 5简单选择排序 32 2 例 设有序列 8325916 排序过程为 i 0 8325916 613 i 1 1 325986 513 i 2 12 35986 400 i 3 123 5986 300 i 4 1235 986 213 i 5 12356 89 100 结果 123568 9 比较逻辑交换物理移动次数次数次数 3 6 5简单选择排序 33 3 算法分析 第一趟排序时进行n 1次比较 第i趟排序时进行n i次比较 总比较次数 比较次数 n n 1 2 移动次数 最坏情况下为3 n 1 时间复杂度 T n O n2 空间复杂度为 O 1 交换记录用 简单选择排序为不稳定排序 3 6 5简单选择排序 34 4 简单选择排序算法C 语言描述 voidSelectSort intv intn inti j k temp for i 0 i n 1 i intk i k存放最小记录位置for j i 1 j n j 找最小记录位置 if v j v k k j if k i 交换第i和第k个位置记录temp v i v i v k v k temp 3 6 5简单选择排序 35 1 线性插入排序1 概念 将一个结点插入到已经排好序的有序表中 得到结点数增1的有序表 3 6 6插入排序 插入排序是将当前无序区中最前端的记录插入到有序区中 逐渐扩大有序区 直到所有记录都插入到有序区中为止 线性 直接 插入排序方法的基本思想是 将记录分为有序和无序两个序列 假定当插入第k个记录时 前面的R1 R2 Rk 1已经排好序 而后面的Rk Rk 1 Rn仍然无序 这时用Rk的关键字与Rk 1的关键字进行比较 若Rk小于Rk 1则将Rk 1向后移动一个单元 再用Rk与Rk 2比较 若Rk小于Rk 2则将Rk 2向后移动一个单元 依次比较下去 直到找到插入位置即将Rk插入 初始状态可以认为有序序列为 R1 36 例 有序列 4 3 5 7 6 1 2 4 排序过程为 r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 4 3576124 5 345 7612412 7 3457 612412 比较次数 物理移动次数 3 6 6插入排序 37 例 有序列 20 6 15 7 3 过程为 r 0 r 1 r 2 r 3 r 4 r 5 6 20 61573 15 620 1573 7 61520 73 3 671520 3 3671520 3 6 6插入排序 38 2 算法分析 比较次数和移动次数与序列原始排列有关 正序 最好情况 逆序 最坏情况 线性插入排序为稳定排序 3 6 6插入排序 39 3 线性 直接 插入排序算法C 语言描述 voidInsertSort intv intn inti j temp for i 1 i0 插入元素 3 6 6插入排序 40 2 对半插入排序1 采用对分查找插入位置 其比较次数较线性插入少 为O nlog2n 移动次数与线性插入相同 为O n2 r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 比较次数 物理移动次数 206132839417285 20 61320283941728537 例 前7个已排好序 3 6 6插入排序 41 交换排序是根据序列中两个结点关键字的比较结果 来对换在序列中的位置 算法的特点是将关键字较大的结点向序列的尾部移动 关键字较小的结点向序列的前部移动 1 冒泡排序1 过程 将待排序的记录 两两进行比较 若相邻两个记录逆序时则交换 这样关键字较小的记录则像气泡一样上浮 而关键字最大的记录则 沉入水底 重复比较 直到不发生交换为止 3 6 7交换排序 42 例 15201110112313 比较逻辑交物理移次数换次数动次数 10111113 152023 300 3 6 7交换排序 43 2 算法分析 正序 最好情况 一次扫描逆序 最坏情况 冒泡排序为稳定排序 3 6 7交换排序 44 3 6 7交换排序 冒泡排序算法C 语言描述 voidBubleSort intv intn inttemp for inti 1 iv j 1 交换两个相邻元素temp v j v j v j 1 v j 1 temp 第i大的元素筛选结束 45 2 快速排序1 算法思想 取表中一个元素 一般选取第一个元素 ai作为控制字 将其放到适当的位置 ai将原序列分成两部分 所有比ai小的元素在ai之前 所有比ai大的元素在ai之后 对分割后的各部分重复 直到每部分只有一个元素为止 3 6 7交换排序 46 例 1110 1315 20 23第二趟排序结果 101113152023第三趟排序结果 3 6 7交换排序 47 例 462622684842368466初始状态 j 2226 36 42 4648 688466 第二趟排序结果 22 26 36424648 66 68 84 第三趟排序结果 48 2 算法分析 比较次数为 O nlog2n 在待排序列已排好序情况下效率最差 T n O n2 快速排序为不稳定排序 讨论 当控制字能把线性表分成两个相等的子区间时 运算效率最高 若关键字位于表首或表尾 如已排好序的情况 则蜕化为冒泡排序 3 6 7交换排序 49 intPartition intlow inthigh intpivot v low 基准对象pivot位置为lowwhile lowpivot high 右边界下移v low v high 小于pivot的放到左侧while low high 下列快速排序中划分序列的算法对v low 与v high 之间的元素进行划分 利用了序列第一个记录作