《(8.2.1)--(23)《数据结构》教案.pdf》由会员分享,可在线阅读,更多相关《(8.2.1)--(23)《数据结构》教案.pdf(6页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 第第8章章 内部排序内部排序(共共 6 时,包括实训内容时,包括实训内容)课题课题 8.1 排序的基本概念 8.2 插入排序 理论理论课时课时 1 学时 实实训训课时课时 1 学时 教学内容教学内容 排序的定义、排序方法的稳定性、排序记录表的建立和输出、直接插入排序、折半插入排序、希尔排序 教学目标教学目标 理解排序的基本概念、掌握各种插入排序的方法 教学重点教学重点 直接插入排序、折半插入排序、希尔排序 教学难点教学难点 希尔排序 教学教学活动及主要活动及主要内容内容 学生活动学生活动 一、创设一、创设情境情境,导入新课(,导入新课(2 分钟)(分钟)(直接导入法直接导入法)导入:在日
2、常办公中,人们会使用 WPS、Excel 等电子表格软件对数据按关键字进行升序或降序的排列。那么计算机如何实现排序?下面我们就来学习排序的基本概念和插入排序 二、新课二、新课讲解讲解(共共计计 16 分钟)(讲解法、提问法、分钟)(讲解法、提问法、演示演示法)法)8.1 8.1 排序的基本概念排序的基本概念 1.排序的定义排序的定义 排序是现实世界中经常进行的一种操作,实质上,排序就是将一组“无序”的序列调整为“有序”的序列的过程。例如,对下列杂乱无章的整数序列 52,49,80,36,14,58,61,23,97,75 经调整后,可改为如下升序序列 14,23,36,49,52,58,6l,
3、75,80,97 给排序下一个较为严格的定义如下。假设含 n 个记录的序列为R1,R2,Rn 其相应的关键字序列为Kl,K2,Kn 这些关键字的排列方式有多种,其中至少有一种排列方式能使得关键字之间存在着这样一个关系:pnppKKK21 按此关系将记录序列重新排列为Rp1,Rp2,Rpn 即为有序记录。将这一过程称为排序排序。2.排序方法的稳定性排序方法的稳定性 上述排序定义中的关键字 Ki可以是记录 Ri(1in)的主关键字,也可以是记录 Ri的次关键字,甚至可以是若干数据项的组合。假设 KiKj(li,jn,ij),且在排序前的序列中 Ri领先于 Rj(即 ij)。若在排序后的序列中 Ri
4、仍领先于Rj,则称所用的排序方法是稳定的;反之,若排序后的序列中可能使 Rj领先于 Ri,则称所用的排序方法是不稳定的。3.排序方法分类排序方法分类 总体上,排序方法分为内部排序内部排序和外部排序外部排序两大类。若整个排序过程不需要访问外存便能完成,则称此类排序为内部排序内部排序;反之,若待排序的记录数量很大,整个序列的排序过程不可能在内存中一次完成,需要借助于外存才能实现,则称 激 发 学 生学习 排 序 的兴趣。学 生 要 理解排 序 的 相关概念 2 此类排序为外部排序外部排序。本章将介绍几种常用的内部排序方法。4.排序记录的数据类型排序记录的数据类型 在本章中介绍的各种排序方法,如不特
5、殊声明,均是指将待排序的记录存于一组连续的空间(数组)上,即顺序存储结构;排序所依据的关键字为整数类型;排序结果要求为升序。待排序的记录数据类型定义如下:#include“stdio.h”#define MAXSIZE 20/*一个用作示例的排序顺序表的最大长度*/typedef int ElemType;/*定义关键字类型为整数类型*/typedef struct ElemType rMAXSIZE+1;/*r 0闲置或用作监视哨*/int length;/*排序记录表长度,即表中的记录个数*/SortList;/*排序记录表类型*/8.2 插入排序插入排序 1直接插入排序直接插入排序 直接
6、插入排序(straight insertion sort)是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增加 1 的有序表。1)基本思想 假设记录序列 R1 n的状态如图 8.2 所示,则一趟直接插入排序的基本思想为:将记录 Ri插入到有序子序列 R1 i-1中,使记录的有序序列从 R1 i-1变为 R1 i。将 Ri的插入过程称作一趟直接插入排序。随着有序区的不断扩大,使 R1 n全部有序,最终完成排序。要将 Ri插入到前面的有序序列中,先将 Ri临时存储到其他单元中,可将其存人 R0单元,作为监视哨。监视哨。然后用 Ri的关键字与前面从第
7、 i-1 个记录开始的关键字进行比较,若 Ri的关键字小,则前面的记录顺序后移,否则将记录 Ri存入空出的位置。2)直接插入排序算法 void InsertSort(SortList*L)/*对记录表 L 作直接插入排序*/int i,j;for(i=2;ilength;i+)/*排序趟数*/if(L-riri-1)/*待插入记录关键字比它前驱记录关键字小*/L-r0=L-ri;/*待排序记录 ri暂存入监视哨位置*/for(j=i-1;L-r0rj;j-)L-rj+1=L-rj;/*比待排序记录关键字大的记录后移*/L-rj+1=L-r0;/*将待排序记录 ri插入到 j+1 位置*/【例
8、8.1】已知序列70,83,100,65,10,32,7,65,9,请给出采用直接插入排序法对该序列进行升序排序的过程。其过程如下图所示。注意:方括号内的数据序列为有序序列,下同。学 生 应 掌握直 接 插 入排序 的 过 程和算 法 并 动手练习 3 (3)算法分析 从空间来看,它只需要一个记录的辅助空间(R0),即 S(n)O(1);从时间来看,直接插入排序算法与待排序记录系列的初始状态有关,n 个记录要进行 n-1 趟插入过程,每一趟都要进行与关键字的比较和记录的移动,但比较的次数是不固定的。最好的情况下是记录已经是排列有序的,则每一趟只需比较一次,就可找到插入记录的位置,不需移动记录,
9、即 T(n)O(n);最坏情况下是记录是反序的,则每一趟都要与前面的所有关键字进行比较并移动记录,即 T(n)O(n)。所以平均时间性能为了 T(n)O(n)。2.折半插入排序折半插入排序 直接插入排序在查找待排序记录位置时使用的是顺序查找。第 7 章介绍了折半查找的性能要比顺序查找好得多,所以在有序序列中查找待插入记录的位置时可以使用折半查找法,由此进行的插入排序称之为折半插入排序(binary insertion sort)。(1)基本思想 因为 R1 i-1是一个按关键字有序的序列,所以先利用折半查找定位记录只Ri在 R1.i中插入位置,再将插入位置开始到下标为 i-1 的记录顺序后移一
10、个位置,最后将 Ri插入到空出位置。(2)折半插入排序算法 void BiInsertSort(SortList*L)/*对顺序表 L 作折半插入排序*/int i,j,low,high,mid;for(i=2;ilength;+i)/*排序趟数*/L-r0=L-ri;/*将待插入记录 ri暂存到 0 号单元*/low=1;high=i-1;while(lowr0rmid)high=mid-1;/*插入位置在低半区*/else low=mid+1;/*插入位置在高半区*/for(j=i-1;j=high+1;-j)/*插入位置及其后的记录顺序后移*/L-rj+1=L-rj;L-rhigh+1=
11、L-r0;/*将待插入记录存入插入位置*/【例 82】已知序列70,83,100,65,10,32,7,65,9,给出采用折半插入排序法对该序列做升序排列的排序过程。学 生 应 掌握折 半 插 入排序 的 过 程和算 法 并 动手练习 4 图 8.2 折半插入排序示例 3)算法分析。从空间来看,折半插入排序所需空间与与直接插入排序相同,即 S(n)O(1),从时间来看,折半插入排序算法与记录序列的初始状态无关,与直接插入排序相比,折半插入排序明显地减少了关键字之间的“比较”次数,但记录“移动”的次数没有改变。因此,折半插入排序的时间复杂度仍为 O(n)。折半插入顺序算法是稳定的排序算法。3希尔
12、排序希尔排序 希尔排序(shellson)又称缩小增量排序缩小增量排序。当待排序记录数较少,且已基本有序时,使用直接插入排序速度较快。希尔排序就是利用直接插入排序的这一优点对待排序的记录序列先作“宏观”调整,再作“微观”调整。1)基本思想 将整个记录序列按下标的一定增量分成若干个序列,对每个子序列分别进行直接插入排序。然后再将增量缩小,划分子序列,分别进行直接插入排序,如此重复进行,最后在对整个序列进行一次直接插入排序。1)希尔插入排序算法 void ShellInsort(SortList*L,int d,int t)/*d 为存放 t 个增量的数组*/int i,j,k;for(k=0;k
13、t;k+)/*增量数*/for(i=dk+1;ilength;+i)/*增量为 dk的排序趟数*/if(L-riri-dk)L-r0=L-ri;/*暂存待插入记录 ri到r0*/for(j=i-dk;j0&L-r0rj;j-=dk)L-rj+dk=L-rj;/*后移*/L-rj+dk=L-r0;/*j+dk为插入位置*/例例 86 已知整数序列70,83,100,65,10,32,7,65,9,增量序列为3.2.1,给出采用希尔插入排序法对该序列做升序排列的排序过程。5 图 8.6 希尔排序示例(3)算法分析 空间上只需一个辅助单元,所以空间复杂性 S(n)O(1)。希尔排序的时间性能计算较为
14、复杂,算法要进行 t 趟,其中 t 为增量序列的长度。每一趟的时间耗费主要在 n/t 个子序列上,时间复杂度约为 O(n4/3)。希尔排序比较适合于处理大批量的杂乱无章的数据序列。另外,从本算法及例 8.6 也可以看出,希尔排序算法是不稳定的。课堂思政:课堂思政:学习学习排序排序,要要善于善于总结总结排序排序方法方法,抓住问题关键,抓住问题关键。三三、归纳总结,再度提升归纳总结,再度提升(1 分钟)(讲解法)分钟)(讲解法)1.排序的基本概念 2.插入排序 四四、作业作业,预习任务预习任务(1 分钟)(激趣法)分钟)(激趣法)课后习题 P247,习题 8:排序的基本概念、插入排序相关习题。预习:8.3 交换排序 8.4 选择排序 学 生 记 录作业 和 预 习内容。6 板 书 设 计 第第 8 8 章章 内部排序内部排序 8.1 8.1 排序的基本概念排序的基本概念 1.排序的定义排序的定义 2.排序方法的稳定性排序方法的稳定性 3.排序方法分类排序方法分类 4.排序记录的数据类型排序记录的数据类型 8.2 插入排序插入排序 1.直接插入排序直接插入排序 2.折半插入排序折半插入排序 3.希尔排序希尔排序