- 1、本文档共32页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构课程的内容结构 第3章 排序 3.1 排序基本概念 4. 什么叫内部排序?什么叫外部排序? 6. 顺序存储(顺序表)的抽象数据类型如何表示? 6. 内部排序的算法有哪些? 3.2 简单排序方法 插入排序 例2:关键字序列T= (21,25,49,25*,16,08),请写出直接插入排序的具体实现过程。 插入排序的算法详细分析: 3.2.2 冒泡排序 冒泡排序的算法分析 直接选择排序 例:关键字序列T= (21,25,49,30,16,08),请给出简单选择排序的具体实现过程。 简单选择排序算法 3.3.1 快速排序 例1:关键字序列 T=(21,25,49,25*,16,08),请写出快速排序的算法步骤。 1.这种不断划分子表的过程,计算机如何自动实现? 例2:关键字序列 T=(21,25,49,25*,16,08),请写出快速排序算法的一趟实现过程。 一趟快速排序算法流程图 整个快速排序的递归算法: 例3:以关键字序列(256,301,751,129,937,863,742,694,076,438)为例,写出执行快速算法的各趟排序结束时,关键字序列的状态。 快速排序算法详细分析: 讨论2. “快速排序”是否真的比任何排序算法都快? 快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数(新的low和high)。 可以证明,函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是我们所讨论的所有内排序方法中最好的一个。 最大递归调用层次数与递归树的深度一致,理想情况为 ?log2(n+1)? 。因此,要求存储开销为 o(log2n)。 如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。此时,快速排序的趟数最少。 * * * 很高兴和大家一起进行教学交流学习 问题 机外表示 处理要求 逻辑结构 基本运算 数学模型 存储结构 实现 实现 建模 求精 3.1 排序基本概念 3.2 简单排序方法 3.3 先进排序方法 3.4 基数排序 3.5 各种排序方法的综合比较 【教学内容】 排序定义及相关概念、插入排序、冒泡排序和直接选择排序的思想及排序过程 【教学要求】 1. 了解排序的定义及相关概念。掌握插入、冒泡和直接选择排序的思想及其依据的原则,对给定关键字的序列能够熟练写出各种排序算法的排序过程。 2. 掌握各种排序方法的时间复杂度。了解各种排序算法的平均情况和最坏情况的时间性能。 3. 理解排序方法“稳定”或“不稳定”的含义。 【重点与难点】 插入、冒泡和选择排序算法的排序过程和算法 各种排序算法的平均情况和最坏情况的时间性能及比较 3.排序算法的好坏如何衡量? 时间效率——排序速度(即排序所花费的全部比较次数) 空间效率——占内存辅助空间的大小 稳定性——若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。 1. 什么是排序? 将一组杂乱无章的数据按一定的规律顺次排列起来。 2. 排序的目的是什么? 存放在数据表中 按关键字排序 ——便于查找! ——若待排序记录都在内存中,称为内部排序; ——若待排序记录一部分在内存,一部分在外存,则称为外部排序。 注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。此处我们仅讨论内部排序。 5.稳定的排序;不稳定的排序(P45) ① 稳定的排序。 ② 不稳定的排序。 排序前:(45,32,67,24,32*,86) 排序后:(24,32,32*,45,67,86)稳定的排序 (24,32*,32,45,67,86)不稳定的排序 注:大多数排序算法都有两个基本的操作:(1)比较两个关键字的大小(2)将记录从一个位置移动到另一个位置,因此采用顺序表结构(便于直接移动元素)。 Typedef struct { //定义每个记录(数据元素)的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RcdType ; Typedef struct { //定义顺序表的结构 RcdType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ; //顺序表类型
您可能关注的文档
- 书法鉴赏(全部经典资料)-(精选·公开·课件).ppt
- 书法--竖的写法(2)-(精选·公开·课件).ppt
- 书愤(精美实用课件)-(精选·公开·课件).ppt
- 书愤717718-(精选·公开·课件).ppt
- 书愤14227711-(精选·公开·课件).ppt
- 书愤课件6301742-(精选·公开·课件).ppt
- 书愤——陆游-(精选·公开·课件).ppt
- 抒情方式-(精选·公开·课件).ppt
- 书籍装帧课件1-(精选·公开·课件).ppt
- 书面表达有效教学-(精选·公开·课件).ppt
- 单元提升卷03 Unit 2 Travelling Around (教师版) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 专题01 基础知识积累运用(学生版) 备战2024-2025学年九年级语文上学期期中真题分类汇编(山东专用).pdf
- 必修二单元提升卷(考试版A4) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 单元提升卷01 选必一Unit 1 People of achievement (教师版) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 2025年高考第一次模拟考试(考试版A4)(参考答案) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 专题06 课内文言文阅读(教师版) 备战2024-2025学年九年级语文上学期期中真题分类汇编(山东专用).pdf
- 单元提升卷05 选必一Unit 5 Working the Land(教师版) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 2025年高考第一次模拟考试(考试版A3)(新高考八省专用) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 2025年高考第一次模拟考试(考试版A4)(新高考专用) 2025年高考英语一轮复习考点通关卷(新高考通用).pdf
- 感谢信的格式和写法(完整版) .pdf
最近下载
- HG╱T 3655-2012 紫外光(UV)固化木器涂料.pdf
- 人民警察警示教育观看心得.docx VIP
- Q-GDW-智能变电站辅助控制系统设计技术规范.pdf
- 外教社2023中国文化英语综合教程 上册 Unit 3 PPT课件(试用版).pptx
- 乡镇临床执业助理医师:甲状腺功能亢进症考试题.docx VIP
- 冀教版七年级上册数学《角的大小》教学说课研讨课件复习.pptx VIP
- 全国智能制造应用技术技能竞赛题及答案.doc VIP
- 智慧园区管理平台建设方案.pdf
- XX职业技术学院关于大数据与会计专业实习的实施方案.docx
- GBT 50034-2024 建筑照明设计标准.docx VIP
文档评论(0)