北京大学数据结构与算法第八章

low
mid
high
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
查找第i个元素： n+1-i
查找失败：
n+1
iii 比较次数=5
顺序查找方法的ASL
n
对含 n个 有记录的 AS表 L ， pici i1
设表中每个元 概素 率的 相 pi查 等 1n找
n
则AS L
i1
pici
1 n i ni1
1n(n1) n2
n1 2
7.2.2 折半查找
1. 折半查找的基本思想 折半查找要求查找表用顺序存储结构存放且各数 据元素按关键字有序（升序或降序）排列，也就是说 折半查找只适用于对有序顺序表进行查找。
查找——也叫检索，是根据给定的某个值，在表中确定一 个关键字等于给定值的记录或数据元素
关键字——是数据元素中某个数据项的值，它可以标识一 个数据元素
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度ASL(Average Search Length)：为确定记 录在表中的位置，需和给定值进行比较的关键字的个 数的期望值叫查找算法的~
7.2 静态查找
正如本章第一节所述：静态查找是指在静态查找 表上进行的查找操作，在查找表中查找满足条件的数 据元素的存储位置或各种属性。本节将讨论以线性结 构表示的静态查找表及相应的查找算法。
7.2.1 顺序查找
1. 顺序查找的基本思想

图8-1内部排序的基本过程
8.2

插入排序
主要思路
不断地将待排序的数据元素插入到有序序列中，使有 序序列逐渐扩大，直至所有数据元素都插入到有序序 列。
直接插入排序和希尔排序
8.2

插入排序
1、直接插入排序
一种比较简单的排序方法
基本思想是依次将记录序列中的每一个记录插入到有 序序列中，使有序序列的长度不断地扩大。
第7趟
第 8趟
(10)
(55)
(10
(10
23
23
27
27
35
35
48
48
60
55
97)
60
55
97)
图8-3直接插入排序的基本过程
8.2

插入排序
2、希尔排序方法
又称为缩小增量排序
基本思路是将待排序的记录划分成几组，从而减少参 与直接插入排序的数据量，当经过几次分组排序后， 记录的排列已经基本有序，这个时候再对所有的记录 实施直接插入排序。
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 第 6趟 第 7趟
(82) (72) (86) (99) (98) (80) (90) (72 (72 (72 (72 (72 (72
72 82) 82 82 82 80 80
{ R1, R2, …， Rn }
关键字序列：{ K1, K2, …，Kn }
K p1 K p2 K pn
R
p1
, R p2 , , R pn

8.1

基本概念

这样通过一趟处理，把待排序记录分成以支点记录 为界的独立的两部分，前面部分记录关键字小于支点记 录关键字，后面部分记录关键字大于支点记录关键字。 然后再按上面方式对每一部分进行同样的分割排序，以 达到整个序列有序（直到每一部分的记录数为1为止）。 快速排序是采用二分法的思想进行排序的方法。 快速排序也是一种交换排序。
冒泡排序算法描述
viod Bubblesort(Sqlist *L) { ElemType temp; int i,j,flag for (i= L->length-1;i>0; --i) { flag=0; for (j=0;j<i;++j) if (L->data[j].key>L.data[j+1].key) { temp=L->data[j];L->data[j]=L->data[j+1]; L->data[j+1]=temp; //交换数据元素 flag=1; //置标识 } if (!flag) break; } }
冒泡排序(续1)
结束标志：若某遍处理无数据交换，说明已排序 好，可提前结束。 若为正序，则只需进行一趟排序，只进行n-1次关 键字比较，无记录移动。 若为逆序，则需进行n-1趟排序，需进行n(n-1)/2次 比较，并做等数量级的记录移动，算法时间复杂度为 O(n2)。 算法中可设置一标志变量flag,每一遍处理开始时, 令其为0，该遍若有数据交换，则置成1。
直接插入排序--算法分析
空间分析：需要一个记录的辅助空间。 时间分析： 1、若记录关键字已按非递减排列，每趟排序插入，只需 进行一次关键字比较，则总的比较次数为n-1。算法时间复杂 度为O(n)。 2、若关键字已按非递增排列,则对第i个记录进行查找插 入时,要比较i次,移动i+1个记录。则总的比较次数为： ∑i=(n+2)(n-1)/2=(n2+n-2)/2 (i=2..n) 移动记录数为∑(i+1)=(n+4)(n-1)/2=(n2+3n-4)/2 平均比较次数=((n2+n-2)/2+n-1)/2=n2/4+3n/4-1≈n2/4 平均移动次数=((n2+3n-4)/2)/2 =n2/2+7n/2-1≈n2/2 则直接插入排序的时间复杂度为O(n2) 直接插入排序为稳定排序。

第8章 排序
本章主要讨论在向量存储方法上各种排序方法的实现。 为了讨论方便，假设待排序记录的关键字均为整数，均从数 组中下标为1的位置开始存储，下标为0的位置存储监视哨或 空闲不用。在本章的各种排序方法中，假定待排序的数据存 放在如下定义的存储结构上，使用C语言，将数据类型描述 如下：
第8章 排序
}Recnode;
Recnode r[Maxsize];
第8章 排序
8.2 插 入 排 序
插入排序的基本思想是：在一个已排好序的记录子集基 础上，一步一步将下一个待排序的记录有序插入到已排好序 的记录子集中，直到将所有待排记录全部插入为止。
第8章 排序
8.2.1 直接插入排序
直接插入排序是一种比较简单的排序方法。其基本思想 是：依次将记录序列中的每一个记录插入到有序段中，使有 序段的长度不断地扩大。其具体的排序过程可以描述如下： 首先将待排序记录序列中的第一个记录作为一个有序段；将 记录序列中的第二个记录插入到上述有序段中形成由两个记 录组成的有序段；再将记录序列中的第三个记录插入到这个 有序段中，形成由三个记录组成的有序段；依此类推。
序的序列。 (5) 基数排序是借助于“分配”和“收集”两种操作来
实现对单逻辑关键字的排序。
第8章 排序
能力要求 针对不同的问题和要求使用各种排序方法解决计算机应
用中的排序问题。 排序在计算机科学中占有相当重要的地位，排序本身就
有着广阔的应用前景。排序，用一个比较通俗的说法就是排 队，可以理解为按规定的次序重新安排给定的一组对象。排 序的目的是便于以后在已排好序的记录集合中查找或检索某 一数据元素。
第8章 排序
8.1 基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 二路归并排序 8.6 基数排序 8.7 排序方法的比较 小结 习题 实训指导