第7单元 排序 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学 计算机教学实验中心
下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学 计算机教学实验中心 第7单元 排序
上节内容提要(1)—查找 查找就是在给定的D中找出满足某种条件的结点;若存在这 样的结点,查找成功;否则,查找失败。(找) ●李找表是一组待查数据元素的集合。待找 ●静态查找是仅仅进行查询和检索操作,不改变查找表中数据 元素间的逻辑关系的查找。(不改变元素关系) 动态查找是除了进行查询和检索操作外,还对查找表进行插 入、删除操作的查找,动态地改变查找表中数据元素之间的逻辑 关系。改变元素关系 平均查找长度 上一页 与关键字进行比较的平均次数。对含有n个数据元素的查找表,查 停止放映找成功时的平均查找长度为 下一页 ASL=∑Pi*Ci Pi为查找第i个数据元素的概率 ●Ci为查找第个数据元素的比较次数。 第2页
下一页 上一页 停止放映 第 2 页 上节内容提要（1）——查找 ⚫ 查找 就是在给定的DS中找出满足某种条件的结点；若存在这 样的结点，查找成功；否则，查找失败。（找） ⚫ 查找表 是一组待查数据元素的集合。待找 ⚫ 静态查找 是仅仅进行查询和检索操作，不改变查找表中数据 元素间的逻辑关系的查找。（不改变元素关系） ⚫ 动态查找 是除了进行查询和检索操作外，还对查找表进行插 入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑 关系。改变元素关系 ⚫ 平均查找长度 与关键字进行比较的平均次数。对含有n个数据元素的查找表，查 找成功时的平均查找长度为 ⚫ Pi 为查找第i个数据元素的概率 ⚫ Ci为查找第i个数据元素的比较次数。 ASL = Pi* Ci n i=1
上节内容提要(2) 顺序查找、 ASL=∑Pi*Ci=1∑(n-i+1)=+1 n 2 折半查找ASL≤log2n 分块查找(索引顺序查找】sgm+1+ n为表长,S为块长 树表查找(二叉排序树)、 上一页 ASL≈log2n 停止放映 哈希查找哈希函数常用的构造方法:数字分析法、平方 下一页 取中法、折叠法、除留余数法(求模取余法)、直接定址法 处理冲突有两种方法:开放地址法(线性探测再散列、二次探测再散 列)、链地址法 第3页
下一页 上一页 停止放映 第 3 页 上节内容提要（2） – 顺序查找、 – 折半查找 ASL – 分块查找（索引顺序查找） –n为表长，S为块长 – 树表查找（二叉排序树）、 ASL – 哈希查找 哈希函数常用的构造方法：数字分析法、平方 取中法、折叠法、除留余数法（求模取余法）、直接定址法 ⚫ 处理冲突有两种方法：开放地址法（线性探测再散列、二次探测再散 列 ）、链地址法 i=1 n 1 2 n+1 n i=1 n ASL = Pi*Ci = (n-i+1) =
本节内容 通过本单元的学习,了解、掌握有关排序的: ●基本概念: 排序、排序分类、算法稳定性 典型的排序算法 插入排序、选择排序、交换排序 快速排序、归并排序 上一页 5种排序方法 停止放映 下一页 第4页
下一页 上一页 停止放映 第 4 页 本节内容 通过本单元的学习，了解、掌握有关排序的： ⚫ 基本概念： –排序、排序分类、算法稳定性 ⚫ 典型的排序算法 –插入排序、选择排序、交换排序 –快速排序、归并排序 –5种排序方法
、排序的基本概念 1.排序( Sorting ●定义: ●将记录按关键字递增(递减)的次序排列起来, 形成新的有序序列,称为排序。 描述: 设n个记录的序列为{R1,R2, 其相应关 键字序列为{K1,K2,…,Kn},需确定一种排序 2,…,Pn,使其相应的关键字满足递增(升 上一页 序)或递减(降序)的关系 Kp1≤Kp2≤..≤Kp 停止放映 或 下一页 Kp1≥Kp2≥…≥Kpn 第5页
下一页 上一页 停止放映 第 5 页 一、排序的基本概念 ⚫ 1.排序(Sorting) ⚫ 定义： ⚫ 将记录按关键字递增(递减)的次序排列起来, 形成新的有序序列,称为排序。 ⚫ 描述： 设n个记录的序列为{R1,R2,…,Rn},其相应关 键字序列为{K1,K2,…,Kn},需确定一种排序 P1,P2,…,Pn,使其相应的关键字满足递增(升 序),或递减(降序)的关系: Kp1 Kp2 ... Kpn 或 Kp1 Kp2 …. Kpn
2.排序分类 ●根据排序元素所在位置的不同,排序分: 内序和外#序 ●内序 在排序过程中,所有元素调到内存中进行 的排序,称为内排序。内排序是排序的基 础 ●外拼序 上一页 在数据量大的情况下,只能分块排序,但 你止放映块与块间不能保证有序。 下一页 第6页
下一页 上一页 停止放映 第 6 页 2.排序分类 ⚫ 根据排序元素所在位置的不同,排序分: 内排序和外排序。 ⚫ 内排序 在排序过程中，所有元素调到内存中进行 的排序，称为内排序。内排序是排序的基 础。 ⚫ 外排序 在数据量大的情况下，只能分块排序，但 块与块间不能保证有序
内排序方法分类 内排序方法的种类 按排序过程中依据的不同原则分类: 插入、选择、归并和基数排序等 按排序过程中所需工作量来区分: 简单排序(0(n2)) 快速排序(0( nlogn)) 基数排序(0(d*n)) 上页·排序过程中所需进行的操作: 停止放映 比较两个关键字的大小 移动记录的位置 下一页 第7页
下一页 上一页 停止放映 第 7 页 内排序方法分类 ⚫ 内排序方法的种类： –按排序过程中依据的不同原则分类： • 插入、选择、归并和基数排序等； –按排序过程中所需工作量来区分： • 简单排序（O（n 2 ）） • 快速排序（O（nlogn）） • 基数排序（O（d*n）） ⚫ 排序过程中所需进行的操作： –比较两个关键字的大小 –移动记录的位置 2
●3排序算法的稳定性 ●若待排序的序列中,存在多个具有相同关键 字的记录,经过排序,这些记录的相对次序 保持不变,则称该算法是稳定的; ●若经排序后,记录的相对次序发生了改变, 则称该算法是不稳定的。 4.算法的评价 上一页 内排序:时间花在比较和移动上,效率用比 较次数来衡量。 停止放映 ●外排序:时间花在读写外存上,用读/写外 下一页 存的次数来衡量其效率(时间复杂度)。 第8页
下一页 上一页 停止放映 第 8 页 ⚫ 3.排序算法的稳定性 ⚫ 若待排序的序列中，存在多个具有相同关键 字的记录，经过排序，这些记录的相对次序 保持不变，则称该算法是稳定的； ⚫ 若经排序后，记录的相对次序发生了改变， 则称该算法是不稳定的。 ⚫ 4.算法的评价 ⚫ 内排序：时间花在比较和移动上，效率用比 较次数来衡量。 ⚫ 外排序：时间花在读写外存上，用读/写外 存的次数来衡量其效率（时间复杂度）
5排序算法的数据结构 ●为简单,这里用顺序存储结构描述待排序 的记录。 ●顺序存储结构(C语言描述): define n struct record int key /*关键字项* int otherterm;/*其它项*/ 上一页 t ypedef struct record RECORD 停止放映 reCoRd filen+1];/米 RECORD型的N+1元数组 下一页 第9页
下一页 上一页 停止放映 第 9 页 ⚫ 为简单，这里用顺序存储结构描述待排序 的记录。 ⚫ 顺序存储结构（C语言描述）： #define N n struct record { int key ； /* 关键字项 */ int otherterm； /* 其它项 */ } ； typedef struct record RECORD； RECORD file[N+1]；/*RECORD型的N+1元数组 5.排序算法的数据结构
、典型排序算法 插入排序 选择排序 交换排序(冒泡) 快速排序 归并排序 上一页 停止放映 下一页 第10页
下一页 上一页 停止放映 第 10 页 二、典型排序算法 • 插入排序 • 选择排序 • 交换排序（冒泡） • 快速排序 • 归并排序