计算机软件基础第四章查找与排序计算机软件基础
4.1 查找与排序概述
4.2 线性表上的查找
4.3 二叉树上的查找
4.4 哈希查找
4.5 直接插入排序
4.6 交换排序
4.7 选择排序
4.8 多关键字排序本章内容
4.1 查找与排序概述
1.与查找有关的概念
(1) 查找：又称检索,是指在大量数据中寻找关键字值等于给定值的记录 。
(2) 主关键字：指在组成记录的若干个数据项中,能够唯一标识一条记录的数据项 。
(3）次关键字：指在组成记录的若干个数据项中，不能唯一标识一条记录的数据项。
计算机软件基础
(4) 平均查找长度 (Average Search Length)指查找过程中,对于查找关键字进行比较的平均比较次数,记为 ASL。 其计算公式如下所示：
其中,pi为查找第 i个元素的概率,ci为查找第 i个元素所需进行的比较次数。通常认为查找每个元素的概率相等，即 p1 = p2 = … = pn =1/n。
n
i
iicpA S L
1
计算机软件基础注意！！：本章所介绍的各种查找方法都是基于主关键字的查找。
2.与排序有关的概念
（ 1） 排序：指将一组记录按照指定关键字大小递增 （ 或递减 ） 的次序排列起来 。
（ 2） 稳定性：若待排序的一组记录中存在多个关键字值相同的记录,如果使用某种排序算法进行排序后,相同关键字值的多个记录的相对次序与排序前相比没有改变,
则称此排序算法具有稳定性 。
计算机软件基础
4.2 线性表的查找
查找方法：
1,顺序查找
2,二分查找
3,分块查找共同点：
都是在顺序存储的线性表上进行查找。
假设后面算法涉及的线性表的类型定义如下 （ 假设关键字类型为 int型 ）,
struct ElemType
{
int key;
datatype other;}；
注意：为了符合习惯，后面顺序线性表查找和排序算法中，元素在数组中的 存储位置从 1开始 。
计算机软件基础一,顺序查找
1,基本思想从线性表的表尾到表头（从后往前），
或者从线性表的表头到表尾（从前往后），
依次将每个元素的关键字值和给定关键字值相比较，寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素，则查找成功；若查找完整个线性表都找不到满足条件的元素，则查找失败。
计算机软件基础
二,算法描述
int SeqSearch(SeqList *L,int x)
/*在线性表上查找关键字为 x的元素 */
{ int i;
L->list[0].key=x; /*设置监视哨 */
i=L->leghth;
/*从表尾开始向前扫描 */
while(L->list[i].key!=x) i--;
return i;
/*若查找成功,返回元素所在的位置；若查找失败,
则返回 0值 */
} /*seqsearch*/
3,算法说明在算法中,线性表中的元素存放于数组 r的下标为 1~
n的数组元素中,为了避免每次比较时都要判断条件
（ i>0） 以防数组下标越界,因此设置了数组元素 r[0]
充当,监视哨,。
4,算法分析当查找成功时，若所查元素为 r(n)，只需一次比较；
若所查元素为 r(1)，需要 n次比较；若所查元素为 r(i)，
则需 n-i+1次比较。因此在等概率条件下查找成功的平均查找长度为：
n
i
n
i
i
n
i
ii
nin
ninpcpA S L 1 11 2
1)1(1)1(
计算机软件基础
计算机软件基础
注意,！
二分查找算法在使用时必须满足两个前提条件：
1,线性表中的元素必须按照查找关键字排列有序；
2,线性表必须以顺序存储方式存储 。
二,二分查找计算机软件基础二,二分查找
1,基本思想找到查找区间的中间位置,用此位置上元素的关键字值与待查关键字值相比较 。 若相等,则查找成功；否则,将查找范围缩小到半个区间,只在可能存在待查元素的前半区间或后半区间进行查找 。 重复上述过程,直到查找成功或查找范围缩小到空 。
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=1 mid=4 high=8
80>45 到右区间查找 改变 low
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=5 mid=6
high=8
80>66 到右区间查找 改变 low
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=7
mid=7 high=8
80=80 查找成功计算机软件基础
二,算法描述
int binsearch(SeqList *L,int x)
/*在长度为 n的升序线性表上查找关键字为 x的元素 */
{ int low,high,mid;
low=1; high=L->length;
/*设置查找区间左,右端点的初值 */
while(low<=high) /*当查找区间非空时进行查找 */
{ mid=(low+high)/2; /*求出区间中间位置 mid的值 */
if(x==L->list[mid].key) return(mid);
/*查找成功时返回元素所在的位置 */
else
{ if(x< L->list[mid].key)
high=mid-1; /*缩小查找区间 */
else low=mid+1;
}
}
return(0); /*查找失败时返回 0值 */
} /*binsearch*/
计算机软件基础
3.算法说明算法中的整型变量 low,high,mid分别用于标识查找区间的左端点、右端点及中间位置。
在 升序 排列的线性表中，若待查元素关键字值小于中间位置元素的关键字值，则缩小查找区间到原区间的上半部（区间左端点不变，区间右端点变为 mid
–1）；若待查元素关键字值大于中间位置元素的关键字值，则缩小查找区间到原区间的下半部（区间右端点不变，区间左端点变为 mid +1）；若待查元素关键字值等于中间位置元素的关键字值，则查找成功，
返回该元素的位置值 mid。
1)1(lo g121 2
1
1
1
nnnkncpA S L
h
k
k
n
i
ii
计算机软件基础在等概率条件下,查找成功时的平均查找长度为：
结论,当 n很大时，二分查找的平均查找长度可近似为 log2(n+1) –1。
4．算法分析计算机软件基础三,分块查找分块查找是性能介于顺序查找和二分查找之间的一种查找方法，又称索引顺序查找。
分块查找的使用前提：
1.将线性表分块,将线性表均匀地分成若干块,块内元素不要求有序,但必须保证块间有序,即后一块中元素的关键字值均大于前一块元素的关键字值；
2.建立索引表,建立由各块中最大关键字值和起始位置两个数据项构成的索引表 ID。
计算机软件基础
例：若需对如下线性表进行分块查找，如何对其分块及建立索引表。
索引表 ID
起始地址
addr
1 6 11
最大关键字值 key
23 48 86
数据表 R
23 15 12 9 20 34 42 36 25 48 60 51 74 86 55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
计算机软件基础
1,基本思想首先在索引表中查找，确定待查元素所在的块；然后在所确定的那一块中查找指定关键字的元素。由于索引表是有序表，查找时可采用二分查找或顺序查找；而在块内查找时，由于块内无序，故只能采用顺序查找。
2,算法描述略。
计算机软件基础
4．算法分析
ASL=ASL索引表 +ASL块内显然,分块查找的效率介于顺序查找和二分查找之间 。
4.1 查找与排序概述
4.2 线性表上的查找
4.3 二叉树上的查找
4.4 哈希查找
4.5 直接插入排序
4.6 交换排序
4.7 选择排序
4.8 多关键字排序本章内容
4.1 查找与排序概述
1.与查找有关的概念
(1) 查找：又称检索,是指在大量数据中寻找关键字值等于给定值的记录 。
(2) 主关键字：指在组成记录的若干个数据项中,能够唯一标识一条记录的数据项 。
(3）次关键字：指在组成记录的若干个数据项中，不能唯一标识一条记录的数据项。
计算机软件基础
(4) 平均查找长度 (Average Search Length)指查找过程中,对于查找关键字进行比较的平均比较次数,记为 ASL。 其计算公式如下所示：
其中,pi为查找第 i个元素的概率,ci为查找第 i个元素所需进行的比较次数。通常认为查找每个元素的概率相等，即 p1 = p2 = … = pn =1/n。
n
i
iicpA S L
1
计算机软件基础注意！！：本章所介绍的各种查找方法都是基于主关键字的查找。
2.与排序有关的概念
（ 1） 排序：指将一组记录按照指定关键字大小递增 （ 或递减 ） 的次序排列起来 。
（ 2） 稳定性：若待排序的一组记录中存在多个关键字值相同的记录,如果使用某种排序算法进行排序后,相同关键字值的多个记录的相对次序与排序前相比没有改变,
则称此排序算法具有稳定性 。
计算机软件基础
4.2 线性表的查找
查找方法：
1,顺序查找
2,二分查找
3,分块查找共同点：
都是在顺序存储的线性表上进行查找。
假设后面算法涉及的线性表的类型定义如下 （ 假设关键字类型为 int型 ）,
struct ElemType
{
int key;
datatype other;}；
注意：为了符合习惯，后面顺序线性表查找和排序算法中，元素在数组中的 存储位置从 1开始 。
计算机软件基础一,顺序查找
1,基本思想从线性表的表尾到表头（从后往前），
或者从线性表的表头到表尾（从前往后），
依次将每个元素的关键字值和给定关键字值相比较，寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素，则查找成功；若查找完整个线性表都找不到满足条件的元素，则查找失败。
计算机软件基础
二,算法描述
int SeqSearch(SeqList *L,int x)
/*在线性表上查找关键字为 x的元素 */
{ int i;
L->list[0].key=x; /*设置监视哨 */
i=L->leghth;
/*从表尾开始向前扫描 */
while(L->list[i].key!=x) i--;
return i;
/*若查找成功,返回元素所在的位置；若查找失败,
则返回 0值 */
} /*seqsearch*/
3,算法说明在算法中,线性表中的元素存放于数组 r的下标为 1~
n的数组元素中,为了避免每次比较时都要判断条件
（ i>0） 以防数组下标越界,因此设置了数组元素 r[0]
充当,监视哨,。
4,算法分析当查找成功时，若所查元素为 r(n)，只需一次比较；
若所查元素为 r(1)，需要 n次比较；若所查元素为 r(i)，
则需 n-i+1次比较。因此在等概率条件下查找成功的平均查找长度为：
n
i
n
i
i
n
i
ii
nin
ninpcpA S L 1 11 2
1)1(1)1(
计算机软件基础
计算机软件基础
注意,！
二分查找算法在使用时必须满足两个前提条件：
1,线性表中的元素必须按照查找关键字排列有序；
2,线性表必须以顺序存储方式存储 。
二,二分查找计算机软件基础二,二分查找
1,基本思想找到查找区间的中间位置,用此位置上元素的关键字值与待查关键字值相比较 。 若相等,则查找成功；否则,将查找范围缩小到半个区间,只在可能存在待查元素的前半区间或后半区间进行查找 。 重复上述过程,直到查找成功或查找范围缩小到空 。
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=1 mid=4 high=8
80>45 到右区间查找 改变 low
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=5 mid=6
high=8
80>66 到右区间查找 改变 low
计算机软件基础
二分查找过程示例下面是在一个升序线性表 {18,26,32，
45,52,66,80,91}上查找关键字为 80的元素的二分查找过程 。
18 26 32 45 52 66 80 91
low=7
mid=7 high=8
80=80 查找成功计算机软件基础
二,算法描述
int binsearch(SeqList *L,int x)
/*在长度为 n的升序线性表上查找关键字为 x的元素 */
{ int low,high,mid;
low=1; high=L->length;
/*设置查找区间左,右端点的初值 */
while(low<=high) /*当查找区间非空时进行查找 */
{ mid=(low+high)/2; /*求出区间中间位置 mid的值 */
if(x==L->list[mid].key) return(mid);
/*查找成功时返回元素所在的位置 */
else
{ if(x< L->list[mid].key)
high=mid-1; /*缩小查找区间 */
else low=mid+1;
}
}
return(0); /*查找失败时返回 0值 */
} /*binsearch*/
计算机软件基础
3.算法说明算法中的整型变量 low,high,mid分别用于标识查找区间的左端点、右端点及中间位置。
在 升序 排列的线性表中，若待查元素关键字值小于中间位置元素的关键字值，则缩小查找区间到原区间的上半部（区间左端点不变，区间右端点变为 mid
–1）；若待查元素关键字值大于中间位置元素的关键字值，则缩小查找区间到原区间的下半部（区间右端点不变，区间左端点变为 mid +1）；若待查元素关键字值等于中间位置元素的关键字值，则查找成功，
返回该元素的位置值 mid。
1)1(lo g121 2
1
1
1
nnnkncpA S L
h
k
k
n
i
ii
计算机软件基础在等概率条件下,查找成功时的平均查找长度为：
结论,当 n很大时，二分查找的平均查找长度可近似为 log2(n+1) –1。
4．算法分析计算机软件基础三,分块查找分块查找是性能介于顺序查找和二分查找之间的一种查找方法，又称索引顺序查找。
分块查找的使用前提：
1.将线性表分块,将线性表均匀地分成若干块,块内元素不要求有序,但必须保证块间有序,即后一块中元素的关键字值均大于前一块元素的关键字值；
2.建立索引表,建立由各块中最大关键字值和起始位置两个数据项构成的索引表 ID。
计算机软件基础
例：若需对如下线性表进行分块查找，如何对其分块及建立索引表。
索引表 ID
起始地址
addr
1 6 11
最大关键字值 key
23 48 86
数据表 R
23 15 12 9 20 34 42 36 25 48 60 51 74 86 55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
计算机软件基础
1,基本思想首先在索引表中查找，确定待查元素所在的块；然后在所确定的那一块中查找指定关键字的元素。由于索引表是有序表，查找时可采用二分查找或顺序查找；而在块内查找时，由于块内无序，故只能采用顺序查找。
2,算法描述略。
计算机软件基础
4．算法分析
ASL=ASL索引表 +ASL块内显然,分块查找的效率介于顺序查找和二分查找之间 。
