《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第9章 排序
85页1、9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较和选择 9.8 外排序简介,第9章 排 序,1、概述 排序是将一组无序的数据元素序列按一定规律进行排列,使其成为有序序列。排序是数据处理中的一种重要运算,如何进行排序,特别是高效率地进行排序是程序设计中所要研究的重要问题之一。 排序在日常生活中也是屡见不鲜的。例如,学生成绩的排名,人事管理部门对职工的排列、运动项目中运动员的排名等,这些均属于排序的例子,排序的目的是便于以后检索其成员,例如,电话号码簿、目录表、图书馆、字词典等一切需对所存对象进行检索的地方,都要先将对象加以排序。,9.1 排序的基本概念,2、排序的定义 假设含有n条记录的序列为 R1,R2,Rn,其相应的关键字序列为 K1,K2,Kn,排序就是将此n条记录按照关键字值的大小递增或递减方式对这些记录进行排列,使这些记录由无序变为有序的一种操作,即排序后得到的序列若为Ri1,Ri2,Rin,则其对应的关键字值满足 Ki1Ki2,Kin或Ki1Ki2,Kin。 3、排序分类 (1)稳定排
2、序与不稳定排序 如果在待排序的记录中,存在有多个关键字相同的记录(如Ri和Rj的关键字相同,即Ki =Kj),若在排序操作之前,Ri在Rj之前,若采用某种排序方法进行排序之后,这些具有相同关键字的记录如Ri和Rj其相对次序保持不变即Ri仍在Rj之前,此时称这种排序方法为稳定排序;相反,若在排序后的序列中Ri与Rj的相对次序发生变化即Ri在Rj之后,此时称这种排序方法是不稳定的。,(2)内排序与外部排序 可根据记录所处的环境即按照排序过程中所使用的内、外存情况的不同,将排序分为内排序和外排序两大类别。若利用某一种排序方法在排序过程中全部数据都存放在内存中即排序时没有进行内、外存数据交换,则称这种排序方法为内排序;若排序过程中全部记录不能同时存放在内存,需要进行数据的内、外存交换,则称这种排序方法为外排序。显然,内排序适用于一些记录数目不很多的文件。对于一些较大的文件,由于内存容量的限制,不能一次全部装入内存进行排序,也只得采用外排序来实现,但是外排序的速度要比内排序速度慢得多。 内排序方法很多,按照排序中所用策略的不同,它一般可分为五类:插入排序、选择排序、交换排序、归并排序和基数排序。
3、每一类中不同的排序算法都是基于同一策略的不同方法。外部排序多是采用多路归并方法进行排序。,4、待排序文件的组织形式与算法评价 以一维数组作为组织形式,排序过程是对记录本身进行物理重排,通过比较和判定把记录移动到合适的位置; 以链表作为组织形式,排序过程中无需移动记录,仅需修改指针即可,通常把这类排序称为表排序; 为待排序文件组织一个辅助表,如组织一张含关键字和指向记录指针的索引表,在排序过程中只需对辅助表的表目进行物理重排,不需移动记录本身,在排序结束后按辅助表调整记录位置。 为了讨论方便起见,假设在内排序中,待排序的n条记录通常被存放在一个一维数组中。 一般通过衡量整个排序过程在最坏或平均情形下进行的记录的比较和移动次数即通过排序的时间复杂性来衡量一个排序算法的好坏。有时还需要分析执行算法所需的附加存储空间和它稳定性和简单性等。,5、数据类型定义 本章如无特别说明,均假设待排序的一组记录存放在一组地址连续的存储单元之中,并设记录关键字均为整数,待排序记录的数据类型为: typedef struct /*记录为一结构型类型*/ int key; /*关键字域*/ elemtype ot
4、heritem; /*记录的其它域*/ recdtype; recdtype Rn ; /*R为一个记录类型数组*/,插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的记录序列的适当位置,直到全部记录插入完成为止。本节将介绍直接插入排序、希尔排序和其它如二分法插入排序、二路插入排序和共享栈插入排序等。 9.2.1 直接插入排序 1、具体做法 直接插入排序是一种最简单的排序方法。它的具体做法是:依次把待排序的记录逐一地按其关键字值的大小插入到一个已排好序的有序序列中,得到一个新的有序序列,直到所有的记录插入完毕为止,从而实现排序。,9.2 插入排序,例如,已知待排序的一组记录对应的关键字为:13,38,22,97,76,65,38,58,而且记录中的前2个记录已按关键字值递增有序即13,38,现要将上面记录中的第三个记录(即关键字22所对应的记录)插入到上述的有序序列中,以得到一个新的含有3个记录的有序序列。 显然,首先需要检索到22的正确插入位置,再进行插入,从而得到一个新的有序序列,其对应的关键字序列为13,22,38,此时称作进行了一趟直接插入排序过
《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第9章 排序》由会员E****分享,可在线阅读,更多相关《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第9章 排序》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页