软件技术基础

Section 5 Search & Sort (查找和排序 查找和排序) 查找和排序

第1页

软件技术基础

学习内容与要求 学习和掌握顺序查找和折半查找算法的原理和 实现； 实现； 学习和掌握二叉排序树的概念及其构造方法、 学习和掌握二叉排序树的概念及其构造方法、 二叉排序树的查找算法原理。 二叉排序树的查找算法原理。 学习和掌握选择排序、交换排序、插入排序、 学习和掌握选择排序、交换排序、插入排序、 归并排序和快速排序方法的原理。 归并排序和快速排序方法的原理。

第2页

软件技术基础

Subsection 1 Search(查找 搜索 查找/搜索 查找 搜索)第3页

软件技术基础

所谓查找(或搜索) 就是在数据 所谓查找(或搜索),就是在数据 查找 集合中寻找满足某种条件的数据对象: 集合中寻找满足某种条件的数据对象: 1.查找成功 1.查找成功 即找到满足条件的 数据对象时, 作为结果, 数据对象时, 作为结果, 可报告该对象 在结构中的位置, 在结构中的位置, 还可给出该对象中的 具体信息。 具体信息。 2.查找不成功 或搜索失败。 2.查找不成功 或搜索失败。作为 结果, 应报告一些信息, 如失败标志、 结果, 应报告一些信息, 如失败标志、 位置等 。第4页

软件技术基础

通常称用于查找的数据集合为查找 通常称用于查找的数据集合为查找 结构，它是由同一数据类型的数据 结构，它是由同一数据类型的数据 或记录)组成。 (或记录)组成。 每个对象有若干属性， 每个对象有若干属性，其中有一个 属性，其值可唯一地标识这个对象， 属性，其值可唯一地标识这个对象， 称为关键字 使用基于关键字 关键字。 关键字的搜 称为关键字。使用基于关键字的搜 查找结果应是唯一的。 索，查找结果应是唯一的。但在实 际应用时，查找条件是多方面的， 际应用时，查找条件是多方面的， 使用基于属性的查找方法， 可以使用基于属性的查找方法 可以使用基于属性的查找方法，但 查找结果可能不唯一 不唯一。 查找结果可能不唯一。第5页

软件技术基础

实施查找时有两种不同的环境静态环境 查找结构不需进行插入和 删除操作。 删除操作。 静态查找表 动态环境 查找过程中可能要对查找 结构执行数据插入、 结构执行数据插入、删除或修改等操 并对查找结构进行调整， 作，并对查找结构进行调整，结构可 能发生变化。 能发生变化。 动态查找表动态查找表的表结构是在查找过程中动态生成 的。第6页

软件技术基础

1. 顺序查找(Sequential Search) 以线性结构表示静态查找表。 以线性结构表示静态查找表。 基本原理：将待查找记录依 基本原理： 次逐个与表中记录进行比较。 次逐个与表中记录进行比较。

第7页

软件技术基础

顺序查找过程(从

前向后查找) 顺序查找过程(从前向后查找)SL.elem

k2 3 4 5 6

k7 8 9 10 11 ST.Length=11

21 37 88 19 92 05 64 56 80 75 130 1

假设给定查找值 e=64, 要求 SL.elem[k] = e, 问: k = ?

第8页

软件技术基础

顺序查找过程(从后向前查找) 顺序查找过程(从后向前查找)0单元用于存放待查找关键字，作为“哨 单元用于存放待查找关键字，作为“ 单元用于存放待查找关键字 兵”(guard) i 返回 返回7 SL.elem0 1 2 3 4 5 6 7 8 9 10

i11

64 21 37 88 19 92 05 64 56 80 75 13

key=64返回0 i 返回SL.elem0 1 2 3 4 5 6 7 8 9

ST.Length=11

i10 11

60 21 37 88 19 92 05 64 56 80 75 13

key=60

ST.Length=11页 第9

软件技术基础

顺序查找算法实现(从后向前查找) 顺序查找算法实现(从后向前查找)int Search_Seq( TB SL, TYPE key ) { SL.elem[0].key = key; // “哨兵” 哨兵” 哨兵 for (i=SL.length; SL.elem[i].key!=key; --i); // 从后往前找 return i; // 查找成功时 为有效下标 否则 为0 查找成功时i为有效下标 否则i为 为有效下标,否则 }

第 10 页

软件技术基础

查找算法的评价指标查找成功: 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 查找失败: 最多比较次数 平均比较次数第 11 页

软件技术基础

查找算法的平均查找长度 查找算法的平均查找长度ASL 平均查找长度 (Average Search Length)指为了确定记录在查找表中的位置， 指为了确定记录在查找表中的位置，需 要和给定值进行关键字比较的次数的期望值 要和给定值进行关键字比较的次数的期望值: 期望值

ASL = ∑ PiCii =1

n

其中， 为表长 为表长， 为查找表中第i个记录的 其中，n为表长，Pi为查找表中第 个记录的 n 概率， 为查找到该记录时， 概率，且 ∑ Pi = 1;Ci为查找到该记录时，曾 i =1 和给定值进行关键字比较的次数。 和给定值进行关键字比较的次数。第 12 页

软件技术基础

在等概率情形， 在等概率情形，查找任一记录的概率 相等： 相等：pi = 1/n, i = 1, 2, …, n

以从前向后顺序查找算法为例， 以从前向后顺序查找算法为例，查找成功时， 查找成功时，ASL succ 1 1 n( n + 1) n + 1 = ∑ i = = . n 2 2 i =1 nn

查找不成功时， 查找不成功时， ASLunsucc

1 = ∑ n = n i =1 n第 13 页

n

查找算法时间复杂度？ 查找算法时间复杂度？ O(n)

软件技术基础

顺序查找算法总结查找长度： 查找长度： 查找成功: 1 查找成功:最少比较次数 n 最多比较次数 平均比较次数 (n+1)/2 查找失败: 查找失败:最少比较次数 n 最多比较次数 n 平均比较次数 n 优点：查找结构无特殊要求( 优点：查找结构无特殊要求(线性结构均适 );算法简单 算法简单； 用);算法简单； 缺点：查找效率较低，不适于大表查找。 缺点：查找效率较低，不适于大表查找。第 14 页

软件技术基础

2. 折半

查找(二分查找) 折半查找(二分查找)(Binary Search)上述按顺序查找表的查找算法 简单，但平均查找长度较大，不适 简单，但平均查找长度较大， 用于表长较大的查找结构。 用于表长较大的查找结构。 若静态查找表为有序表， 若静态查找表为有序表，则查找 有序表 过程可以基于“折半”进行。 过程可以基于“折半”进行。第 15 页

软件技术基础

基于有序顺序表的折半查找个数据对象存放在一个有序顺序表中 设 n个数据对象 存放在一个有序顺序表中 ， 个数据对象 存放在一个有序顺序表中， 并按其关键字值从小到大(或从大到小) 并按其关键字值从小到大(或从大到小) 排好序。 排好序。 原理：折半查找时, 每次都先求出位于查 原理 ： 折半查找时 每次都先求出位于 查 找区间正中的对象的下标 正中的对象的下标mid, 用其关键 找区间 正中的对象的下标 ， 字与给定值 比较， 给定值x比较 字与 给定值 比较 ， 然后根据比较结果将 查找区间缩小一半 直至找到被查找对象。 缩小一半， 查找区间缩小一半，直至找到被查找对象。第 16 页