《数据结构》课程电子教案(PPT课件讲稿,C语言版)第10章 内排序
第10章内排序 排序是数据处理过程中经常使用的一种重要的运 算,排序的方法有很多种,本章主要讨论内排序的各 种算法,并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论。 10.1排序的基本概念 假设一个文件是由n个记录R1,R2,…,,R1组成 所谓排序就是以记录中某个(或几个)字段值不減(可 不增)的次序将这n个记录重新排列,称该字段为排 序码。能唯标识一个记录的字段称为关键码,关 键码可以作为排序码,但排序码不一定要是关键码
第10章 内排序 排序是数据处理过程中经常使用的一种重要的运 算,排序的方法有很多种,本章主要讨论内排序的各 种算法,并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论。 10.1 排序的基本概念 假设一个文件是由n个记录R1,R2,…,Rn组成, 所谓排序就是以记录中某个(或几个)字段值不减(或 不增)的次序将这n个记录重新排列,称该字段为排 序码。能唯一标识一个记录的字段称为关键码,关 键码可以作为排序码,但排序码不一定要是关键码
按排序过程中使用到的存储介质来分,可以将排 序分成两大类:内排序和外排序 内排序是指在排序过程中所有数据均放在内存中 处理,不需要使用外存的排序方法。而对于数据量很 大的文件,在内存不足的情況下,则还需要使用外存 这种排序方法称为外排序。 排序码相同的记录,若经过排序后,这些记录 仍保持原来的相对次序不变,称这个排序算法是稳 定的。否则,称为不稳定的排序算法
按排序过程中使用到的存储介质来分,可以将排 序分成两大类:内排序和外排序。 内排序是指在排序过程中所有数据均放在内存中 处理,不需要使用外存的排序方法。而对于数据量很 大的文件,在内存不足的情况下,则还需要使用外存, 这种排序方法称为外排序。 排序码相同的记录,若经过排序后,这些记录 仍保持原来的相对次序不变,称这个排序算法是稳 定的。否则,称为不稳定的排序算法
评价排序算法优劣的标准 首先考虑算法执行所需的时间,这主要是用执行 过程中的比较次数和移动次数来度量; 其次考虑算法执行所需要的附加空间。 当然,保证算法的正确性是不言而喻的,可读性等 也是要考虑的因素
评价排序算法优劣的标准 : 首先考虑算法执行所需的时间,这主要是用执行 过程中的比较次数和移动次数来度量; 其次考虑算法执行所需要的附加空间。 当然,保证算法的正确性是不言而喻的,可读性等 也是要考虑的因素
排序算法如未作特别的说明,使用的有关定义如下 /常见排序算法的头文件,文件名 table. h # define MaXsize100/文件中记录个数的最大值 typedef int keytype;/定义排序码类型为整数类型 typedef struct keytype key 为了方便,『0]一般不用 于存放排序码,在一些排序 /此处还可以定义记录中除 算法中它可以用来作为中间 frecordtype 记录单元存放临时数据。 length typedef struct 域是待排序的记录个数,它 必须不大于 MAXSIZE,这样 recordtype「 MAXSIZE+1 第1 length个记录的排序码 int length 待排分别存于 Stable /待排序r1key- r[length]. key中
排序算法如未作特别的说明,使用的有关定义如下 : /*常见排序算法的头文件,文件名table.h*/ #define MAXSIZE 100 /*文件中记录个数的最大值*/ typedef int keytype; /*定义排序码类型为整数类型*/ typedef struct{ keytype key; /*此处还可以定义记录中除排序码外的其它域*/ }recordtype; /*记录类型的定义*/ typedef struct{ recordtype r[MAXSIZE+1]; int length; /*待排序文件中记录的个数*/ }table; /*待排序文件类型*/ 为了方便,r[0]一般不用 于存放排序码,在一些排序 算法中它可以用来作为中间 单元存放临时数据。length 域是待排序的记录个数,它 必须不大于MAXSIZE,这样, 第1~length个记录的排序码 分别存于 r[1].key~r[length].key中
102插入排序 插入排序的基本方法是: 将待排序文件中的记录,逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 1021直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第个记录R进行 插入时,R1,R21…,R1已排序,将记录R的排序码 key与已经排好序的排序码从右向左依次比较,找到R 应插入的位置,将该位置以后直到R各记录顺序后移, 空出该位置让R插入
10.2 插入排序 插入排序的基本方法是: 将待排序文件中的记录, 逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 10.2.1 直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第i个记录Ri进行 插入时,R1,R2,…,Ri-1已排序,将记录Ri的排序码 keyi与已经排好序的排序码从右向左依次比较,找到Ri 应插入的位置,将该位置以后直到Ri-1各记录顺序后移, 空出该位置让Ri插入
组记录的排序码分别为 312,126,272,226,28,165,123 初始时将第1个排序码作为已经排好序的,把排好序 的数据记录放入中括号[中,表示有序的文件,剩下 的在中括号外,如下所示 312],126,272,226,28,165,123 设前3个记录的排序码已重新排列有序,构成一个含 有3个记录的有序文件 [126,272,312],226,28,165,123 现在要将第4个排序码226插入
一组记录的排序码分别为: 312,126,272,226,28,165,123 初始时将第1个排序码作为已经排好序的,把排好序 的数据记录放入中括号[]中,表示有序的文件,剩下 的在中括号外,如下所示: [312],126,272,226,28,165,123 设前3个记录的排序码已重新排列有序,构成一个含 有3个记录的有序文件: [126,272,312],226,28,165,123 现在要将第4个排序码226插入 !
[126,272,312],226,28,165,123 现在要将第4个排序码226插入 将待插入的排序码226和已经有序的最后一个排 序码312比较,因为待插入的排序码226小于312,所 以226肯定要置于312的前面,至于是否就是置于312 的前一个位置,此时还不能确定,需要继续向左比较; 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置,在空出的位置插入待 排序的排序码226,得含有4个记录的有序文件 [126,226,272,312],28,165,123
[126,272,312],226,28,165,123 现在要将第4个排序码226插入 ! 将待插入的排序码226和已经有序的最后一个排 序码312比较,因为待插入的排序码226小于312,所 以226肯定要置于312的前面,至于是否就是置于312 的前一个位置,此时还不能确定,需要继续向左比较; 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置,在空出的位置插入待 排序的排序码226,得一含有4个记录的有序文件: [126,226,272,312],28,165,123
需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时 [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨
需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时: [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨 兵
void insertsort(table*tab for(i=2; Length; i++)/次插入从第2个开始的所有元素 j=i-1; tab->r[o]key=tab>]key/"设置哨兵,准备找插入位置 While(tab->r0]keyrj]key)/找插入位置并后移 tab->j+1]key=tab->key;/后移 继续向前(左)查找* tab->rj+1]key=tab->ro]key;/插入第个元素的副本,即前面设置的哨兵 算法10.1直接插入排序算法
void insertsort(table *tab) { int i,j; for(i=2;ilength;i++)/*依次插入从第2个开始的所有元素*/ { j=i-1; tab->r[0].key=tab->r[i].key;/*设置哨兵,准备找插入位置*/ while(tab->r[0].keyr[j].key) /*找插入位置并后移*/ { tab->r[j+1].key=tab->r[j].key; /*后移*/ j=j-1; /*继续向前(左)查找*/ } tab->r[j+1].key=tab->r[0].key; /*插入第i个元素的副本,即前面设置的哨兵*/ } } 算法10.1 直接插入排序算法
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第09章 检索.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第08章 图(李云清、杨庆红、揭安全).ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第07章 二叉树.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第06章 树型结构.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第05章 递归.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第04章 字符串、数组和特殊矩阵.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第1章 概论、第2章 线性表及其顺序存储、第3章 线性表的链式存储.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第1章 概论、第2章 线性表及其顺序存储、第3章 线性表的链式存储.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第1章 概论、第2章 线性表及其顺序存储、第3章 线性表的链式存储.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第十章 指针.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第九章 预处理命令.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第八章 函数.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)C程序设计实验讲义.doc
- 《C语言程序设计》课程教学资源(PPT课件讲稿)06年C程序设计实验教学大纲.doc
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第十三章 文件.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第十一章 结构体与共用体.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第一章 C语言概述.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)部分习题答案(前三章).doc
- 《C语言程序设计》课程教学资源(PPT课件讲稿)选择结构实验2.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)选择结构2.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第11章 外排序.ppt
- 《数据结构》课程电子教案(PPT课件讲稿,C语言版)第12章 动态存储管理.ppt
- 长江大学:《C语言程序设计》PPT课件_第五章 选择结构程序设计(1/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第四章 简单C程序设计.ppt
- 长江大学:《C语言程序设计》PPT课件_第三章 数据类型、运算符与表达式(2/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第三章 数据类型、运算符与表达式(1/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第二章 计算机算法(2/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第二章 计算机算法(1/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第一章 C语言概述.ppt
- 长江大学:《C语言程序设计》PPT课件_第十三章 文件.ppt
- 长江大学:《C语言程序设计》PPT课件_第十二章 位运算.ppt
- 长江大学:《C语言程序设计》PPT课件_第十一章 结构体与共用体(2/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第十一章 结构体与共用体(1/2).ppt
- 长江大学:《C语言程序设计》PPT课件_第十章 指针(3/3).ppt
- 长江大学:《C语言程序设计》PPT课件_第十章 指针(2/3).ppt
- 长江大学:《C语言程序设计》PPT课件_第十章 指针(1/3).ppt
- 长江大学:《C语言程序设计》PPT课件_第九章 预处理命令.ppt
- 长江大学:《C语言程序设计》PPT课件_第八章 函数(3/3).ppt
- 长江大学:《C语言程序设计》PPT课件_第八章 函数(2/3).ppt
- 长江大学:《C语言程序设计》PPT课件_第八章 函数(1/3).ppt