第四章 慧查找与排序
计算机软件基础 第四章 查找与排序
本章内容 今4.1查找与排序概述 计算机软件基 今42线性表上的查找 今4.3二又树上的查找 4.4哈希查找 ◆4.5直接插入排序 ◇4.6交换排序 今47选择排序 4.8多关键字排序
计算机软件基础 ❖ 4.1 查找与排序概述 ❖ 4.2 线性表上的查找 ❖ 4.3 二叉树上的查找 ❖ 4.4 哈希查找 ❖ 4.5 直接插入排序 ❖ 4.6 交换排序 ❖ 4.7 选择排序 ❖ 4.8 多关键字排序 本章内容
41查找与排序概述 计1与查找有关的概念 ()查找:又称检索,是指在大量数据中寻找 件关键字值等于给定值的记录。 基(2)主关键字:指在组成记录的若干个数据项 础中,能够唯一标识一条记录的数据项。 (3)次关键字:指在组成记录的若干个数据 项中,不能唯一标识一条记录的数据项
4.1 查找与排序概述 1.与查找有关的概念 (1) 查找：又称检索，是指在大量数据中寻找 关键字值等于给定值的记录。 (2) 主关键字：指在组成记录的若干个数据项 中，能够唯一标识一条记录的数据项。 (3）次关键字：指在组成记录的若干个数据 项中，不能唯一标识一条记录的数据项。 计 算 机 软 件 基 础
(4)平均查找长度( Average Search Length指 查找过程中,对于查找关键字进行比较的平均 计比较次数,记为4其计算公式如下所示 ASL=∑pc 件其中,P为查找第个元素的概率,c为查找 基第个元素所需进行的比较次数。通常认为查找 每个元素的概率相等,即p1=p2=…=pn=1n 注意!!:本章所介绍的各种查找方法都是 基于主关键字的查找
(4) 平均查找长度(Average Search Length)指 查找过程中，对于查找关键字进行比较的平均 比较次数，记为ASL。其计算公式如下所示： 其中，pi为查找第i个元素的概率， ci为查找 第i个元素所需进行的比较次数。通常认为查找 每个元素的概率相等，即p1 = p2 = … = pn =1/n。 = = n i ASL pici 1 计 算 机 软 件 基 础 注意！！：本章所介绍的各种查找方法都是 基于主关键字的查找。
2.与排序有关的概念 计算机软件基 (1)排序:指将一组记录按照指定关键字 大小递增(或递减)的次序排列起来。 (2)稳定性:若待排序的一组记录中存在 但多个关键字值相同的记录,如果使用某种 排序算法进行排序后,相同关键字值的多 个记录的相对次序与排序前相比没有改变, 则称此排序算法具有稳定性
2.与排序有关的概念 （1）排序：指将一组记录按照指定关键字 大小递增（或递减）的次序排列起来。 （2）稳定性：若待排序的一组记录中存在 多个关键字值相同的记录，如果使用某种 排序算法进行排序后，相同关键字值的多 个记录的相对次序与排序前相比没有改变， 则称此排序算法具有稳定性。 计 算 机 软 件 基 础