文档介绍：第五章
查找与排序算法
查找与排序概述
(1) 查找:又称检索,是指在大量数据中寻找关键字值等于给定值的记录。
(2) 主关键字:指在组成记录的若干个数据项中,能够唯一标识一条记录的数据项。
(3)次关键字:指在组成记录的若干个数据项中,不能唯一标识一条记录的数据项。
(4) 平均查找长度(Average Search Length)指查找过程中,对于查找关键字进行比较的平均比较次数,记为ASL。其计算公式如下所示:
其中,pi为查找第i个元素的概率, ci为查找第i个元素所需进行的比较次数。通常认为查找每个元素的概率相等,即p1 = p2 = …= pn =1/n。
计算机软件基础
注意!!:本章所介绍的各种查找方法都是基于主关键字的查找。
(1)排序:指将一组记录按照指定关键字大小递增(或递减)的次序排列起来。
(2)稳定性:若待排序的一组记录中存在多个关键字值相同的记录,如果使用某种排序算法进行排序后,相同关键字值的多个记录的相对次序与排序前相比没有改变,则称此排序算法具有稳定性。
稳定性举例
计算机软件基础
线性表的查找
查找方法:
顺序查找
二分查找
分块查找
共同点:
都是在顺序存储的线性表上进行查找。
后面算法所出现的线性表的类型定义(假设查找或排序关键字为KeyType类型)
typedef struct
{ KeyType key;
OtherType other;
}DataType;
typedef struct
{ DataType list[MAXLEN];
int length;
}SeqList;
注意:为了符合大多数人的一般****惯,本章在采用顺序存储方式存放线性表元素时数组下标均从1开始。
计算机软件基础
一. 顺序查找
从线性表的表尾到表头(从后往前),或者从线性表的表头到表尾(从前往后),依次将每个元素的关键字值和给定关键字值相比较,寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素,则查找成功;若查找完整个线性表都找不到满足条件的元素,则查找失败。
计算机软件基础
int SeqSearch(SeqList *L,KeyType x)
/*在线性表上查找关键字为x的元素*/
{ int i;
L->list[0].key=x; /*设置监视哨*/
i=L->length;
/*从表尾开始向前扫描*/
while(L->list[i].key!=x) i--;
return i;
/*若查找成功,返回元素所在的位置;若查找失败,则返回0值*/
} /*seqsearch*/
3. 算法说明
在算法中,线性表中的元素存放于数组r的下标为1~ n的数组元素中,为了避免每次比较时都要判断条件(i>0)以防数组下标越界,因此设置了数组元素list[0]充当“监视哨”。
4. 算法分析
当查找成功时,若所查元素为list[n],只需一次比较;若所查元素为list[1],需要n次比较;若所查元素为list[i],则需n-i+1次比较。因此在等概率条件下查找成功的平均查找长度为:
计算机软件基础
计算机软件基础
二. 二分查找
找到查找区间的中间位置,用此位置上元素的关键字值与待查关键字值相比较。若相等,则查找成功;否则,将查找范围缩小到半个区间,只在可能存在待查元素的前半区间或后半区间进行查找。重复上述过程,直到查找成功或查找范围缩小到空。