第四部分 查找与排序技术(new).ppt

2 6查找与排序 2 6 1查找的基本概念 所谓查找 根据一个给定的元素 在数据结构中根据不同策略确定符合给定元素值的数据元素的过程 2 6 2静态查找技术 根据策略可以分成三大类 1 顺序查找法2 有序表的对分查找法3 分块查找法 1顺序查找法 顺序查找法又称为顺序搜索法 基本方法如下 1 从线性表的第一个元素开始 依次将线性表中元素与给定元素的值进行比较 2 相等则表示找到 否则表示失败 如果遍历了整个表都没有找到 说明表中没有要找的元素 从上面的方法来看 其顺序查找的效率很低 但在以下两种情况中 却只能使用顺序查找法 1 线性表是无序表2 采用链式存储的有序线性表 2有序表的对分查找法 对分查找法 只应用于顺序存储的有序表 假设有序线性表的长度为n 被查元素为x 则对分法如下 1 将x与线性表的中间项进行比较 若中间项的值等于x 说明查找成功 2 若x小于中间项 则在表的前面部分进行相同的查找 否则在表的后面部分进行查找 3 此过程直到查找成功或者子表长度为0时结束 对分查找法在最坏的情况下 也只比较log2N次 算法程序 intsearch SL List int v intstart intend intx intk while start end k start end 2 if v k x returnk if v k x start k 1 elseend k 1 return 1 3分块查找 分块查找又称索引顺序查找 它是一种顺序查找的改进策略 用于在分块有序表中查找 所谓分块是指将长度为N的线性表分成M个子表 各子表的长度可以相等 也可以不相等 但要求后一子表的每一个元素都要大于前一个子表的所有元素 分块有序表的结构可以分为两部分 1 线性表本身是顺序存储结构2 再建立一个索引表 线性表中每个子表建立一个索引节点 索引节点包括两部分 一是数据域 一是指针域 数据域存放对应子表中的最大元素值 指针域用于指示子表第一个元素的在整个表中序号 3分块查找 上图查找过程 首先查找索引表 确定查找的子表 然后再相应的子表中应顺序表查找法查找 structindnode intkey intk 二叉排序树的定义二叉排序树可能为一棵空的二叉树 若非空则必须满足以下特征 1 根结点左子树中所有结点的关键字小于根结点的关键字 2 根结点右子树中所有结点的关键字大于或等于根结点的关键字 3 根结点的左右子树也都是二叉排序树 一棵二叉排序树 2 6 3动态查找技术 建立了二叉排序树之后 若查找过程中不插入或删除元素 静态查找 则在二叉排序树中查找方法为 1 将给定数据key与根结点关键字x进行比较 若key x则查找成功 2 若keyx 则与右子树的根结点的关键字值进行比较 重复上述步骤 直到查找成功 或者一直比较到叶子结点也找不到目标元素 则查找失败 可定义二叉排序树结点如下 typedefstructNode KeyTypex 关键字structNode left right BinNode typedefBinNode BinNodePtr 二叉排序树查找算法 静态查找 实现 BinNode search btree BinNodePtrp KeyTypekey while p NULL 进行动态查找时 查找过程还涉及到插入新结点 其方法为 1 在二叉排序树中查找数据key 按前一页的方法 若查找成功则程序中止 若查找失败则转入下面插入过程 2 2 以数据key作为关键字建立新结点 假定查找过程最后到达某叶子结点 比较key与此叶子结点的关键字 若key小于后者则将新结点插入为叶子结点的左孩子 若key大于后者则新结点插入为叶子结点的右孩子 例 动态查找 10 6 19 22 8 2 动态查找过程也是生成二叉排序树的过程 假定由整数序列 10 6 19 22 8 2 生成一棵二叉排序树 可以采用逐个元素插入的方法实现 1 首先将10作为根结点 2 然后插入6时 通过比较知6 10 所以将6作为10的左孩子插入 3 同理将19作为10的右孩子插入 4 整数22通过和10 19比较后 作为19的右孩子插入 5 依次插入剩余的其他元素 二叉排序树动态查找算法实现如下 BinNode Search Insert BinNodePtrp KeyTypekey BinNode pre NULL 循环查找过程while p NULL 查找失败 插入新结点 见下一页 接上一页内容 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 返回找到的结点或插入的新结点的指针 2 6 4排序基本概念 排序是计算机内经常进行的一种操作 其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列 排序的形式化定义为 假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系Kp1 Kp2 Kpn 按此固有关系将最初的记录序列重新排列为 Rp1 Rp2 Rpn 的操作称作排序 根据是否需要访问外存 排序分为内部排序和外部排序 内部排序方法有很多类型 按方法实现特点可分为插入排序 选择排序 交换排序 归并排序等等 按方法效率可分为简单的排序法 先进的排序法等等 简单的排序法包括插入排序 选择排序 冒泡排序等 它们的时间复杂度为O n2 而先进的排序法包括快速排序 归并排序等 它们的时间复杂度大约为O nlog2n 2 6 5常用排序方法 1 直接插入排序将记录分为有序和无序两个序列 假定当插入第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 例 对序列 35 22 16 19 22 进行排序 初始状态 35 22161922第1趟 2235 161922第2趟 162235 1922第3趟 16192235 22第4趟 1619222235 直接插入排序执行过程 显示在序列 35 22 16 19 22 上应用插入排序的过程 为了对序列中相同记录加以区别 使用了下划线 直接插入排序算法实现 voidInsertSort intv intn inti j temp for i 1 i0 插入元素 2 简单选择排序简单选择排序的基本思想是 将记录分为有序和无序两个序列 假定第k趟排序时 前面的R1 R2 Rk 1已经排好序 而后面的Rk Rk 1 Rn仍然无序 选择Rk到Rn中的关键字最小的记录与Rk交换 交换后有序序列增加了第k个记录 当第n 1趟选择执行完 待排序记录只剩下1个 就不用再选了 在初始状态可以认为有序序列为空 例 对序列 35 22 16 19 22 进行排序 在序列 35 22 16 19 22 上应用简单选择排序的过程 初始状态 3522161922 第1趟 16 22351922 第2趟 1619 352222 第3趟 161922 3522 第4趟 16192222 35 简单选择排序算法实现 voidSelectSort intv intn inti j 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 冒泡排序冒泡排序的基本思路是 第一趟排序对全部记录R1 R2 Rn自左向右顺次两两比较 若Rk大于Rk 1则交换Rk和Rk 1 k 1 2 n 1 第一趟排序完成后Rn成为序列中最大记录 第二趟排序对序列前n 1个记录采用同样的比较和交换方法 第二趟排序完成后Rn 1成为序列中仅比Rn小的次大的记录 第三趟排序对序列前n 2个记录采用同样处理方法 如此做下去 最多做n 1趟排序 整个序列就排序完成 例 对序列 35 22 16 19 22 进行排序 下图显示了在序列 35 22 16 19 22 上应用冒泡排序的过程 初始状态 35221619 22第1趟 22161922 35 第2趟 161922 22 35 第3趟 1619 2222 35 第4趟 16 192222 35 冒泡排序算法实现 voidBubleSort intv intn inttemp for inti 1 iv j 1 交换两个相邻元素temp v j v j v j 1 v j 1 temp 第i大的元素筛选结束 4 快速排序快速排序的基本思想是 任取待排序序列中某个记录S 例如取第一个记录 作为基准 经过一系列比较和交换 将整个序列划分为如下形式 左侧子序列 S 右侧子序列 并且满足以下两点 左侧子序列中所有记录的关键字都小于或等于基准对象S的关键字 右侧子序列中所有记录的关键字都大于或等于基准对象S的关键字然后分别对左右两个子序列重复施行上述方法 直到排序完成 在 22 35 27 16 45 19 22 上应用划分算法 即一趟快速排序 下列快速排序中划分序列的算法对v low 与v high 之间的元素进行划分 利用了序列第一个记录作为基准 最终将low与high区间中的序列划分为左右两个子序列 将基准对象放到适当位置并返回其位置的下标 intPartition intlow inthigh intpivot v low 基准对象pivot位置为lowwhile low pivot high 右边界下移v low v hi