puter主讲赵英良西安交通大学计算.ppt

计算机软件基础
The software basic puter
主讲:赵英良
西安交通大学
计算机教学实验中心
第7单元
排序
10/26/2017
1
上节内容提要(1)——查找
查找就是在给定的DS中找出满足某种条件的结点;若存在这样的结点,查找成功;否则,查找失败。(找)
查找表是一组待查数据元素的集合。待找
静态查找是仅仅进行查询和检索操作,不改变查找表中数据元素间的逻辑关系的查找。(不改变元素关系)
动态查找是除了进行查询和检索操作外,还对查找表进行插入、删除操作的查找,动态地改变查找表中数据元素之间的逻辑关系。改变元素关系
平均查找长度
与关键字进行比较的平均次数。对含有n个数据元素的查找表,查找成功时的平均查找长度为
Pi 为查找第i个数据元素的概率
Ci为查找第i个数据元素的比较次数。
ASL =  Pi* Ci
n
i=1
2
上节内容提要(2)
顺序查找、
折半查找 ASL 
分块查找(索引顺序查找)
n为表长,S为块长
树表查找(二叉排序树)、
ASL 
哈希查找哈希函数常用的构造方法:数字分析法、平方取中法、折叠法、除留余数法(求模取余法)、直接定址法
处理冲突有两种方法:开放地址法(线性探测再散列、二次探测再散列)、链地址法
i=1
n
1
2
n+1
n
i=1
n
ASL =  Pi*Ci = (n-i+1) =
3
本节内容
通过本单元的学习,了解、掌握有关排序的:
基本概念:
排序、排序分类、算法稳定性
典型的排序算法
插入排序、选择排序、交换排序
快速排序、归并排序
5种排序方法
4
一、排序的基本概念
(Sorting)
定义:
将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。
描述:
设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:
Kp1  Kp2 ... Kpn
或
Kp1  Kp2 ….  Kpn
5

根据排序元素所在位置的不同,排序分:
内排序和外排序。
内排序
在排序过程中,所有元素调到内存中进行的排序,称为内排序。内排序是排序的基础。
外排序
在数据量大的情况下,只能分块排序,但块与块间不能保证有序。
6
内排序方法分类
内排序方法的种类:
按排序过程中依据的不同原则分类:
插入、选择、归并和基数排序等;
按排序过程中所需工作量来区分:
简单排序(O(n2 ))
快速排序(O(nlogn))
基数排序(O(d*n))
排序过程中所需进行的操作:
比较两个关键字的大小
移动记录的位置
2
7

若待排序的序列中,存在多个具有相同关键字的记录,经过排序,这些记录的相对次序保持不变,则称该算法是稳定的;
若经排序后,记录的相对次序发生了改变,则称该算法是不稳定的。

内排序:时间花在比较和移动上,效率用比较次数来衡量。
外排序:时间花在读写外存上,用读/写外存的次数来衡量其效率(时间复杂度)。
8
为简单,这里用顺序存储结构描述待排序的记录。
顺序存储结构(C语言描述):
#define N n
struct record {
int key ; /* 关键字项*/
int otherterm; /* 其它项*/
} ;
typedef struct record RECORD;
RECORD file[N+1];/*RECORD型的N+1元数组

9
二、典型排序算法
插入排序
选择排序
交换排序(冒泡)
快速排序
归并排序
10