数据结构-排序_第1页
数据结构-排序_第2页
数据结构-排序_第3页
数据结构-排序_第4页
数据结构-排序_第5页
已阅读5页，还剩1页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

运城职业技术大学教案(本科）20—20学年第学期课程名称数据结构课程性质学时授课班级授课教师教案首页教学单元名称第十章内部排序第2节排序算法教学内容1.排序的定义2.插入排序和选择排序课时2授课地点教室授课所需教具、工具、软件、耗材等多媒体、黑板、粉笔教学目标知识目标能力目标素质目标通过学习不同的排序方法，体会不同的排序思维对排序效率的影响，形成自己对排序的理解，开拓思维，注重创新教学重难点重点难点教学方法与手段讲授、演示、讨论、案例分析、实验课程资源备注教案一、导入新课（5分钟）通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以采用查找效率较高的折半查找法，其平均查找长度为log2(n+1)-1,而无序的顺序表只能进行顺序查找，其平均查找长度为(n+1)/2。因此，本次课我们学习排序算法。二、讲授新课（75分钟）1.排序的定义（10分钟）假设含n个记录的序列为：{R1,R2,…,Rn}其对应的关键字序列为：{K1,K2,…,Kn}需确定1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字满足如下的非递减（或非递增）关系：Kp1≤Kp2≤…≤Kpn使其成为一个按关键字有序的序列：{Rp1,Rp2,…,Rpn}假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i<j）。若在排序后的序列中Ri领先于Rj则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri,则称所用的排序方法是不稳定的。2.直接插入排序（10分钟）直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到巳排好序的有序表中，从而得到一个新的、记录数增1的有序表。例如，已知待排序的一组记录的初始排列如下所示：R(49)，R(38)，R(65)，R(97)，R(76)，R(13)，R(27)，R(49)3.希尔排序（20分钟）希尔排序又称缩小增量排序，也属于插入类排序，但时间效率上有了很大改进。它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。例如：注意：这三趟排序的增量分别是5、3、1。4.冒泡排序（15分钟）冒泡排序是一种借助“交换”进行排序的办法，每一趟排序都使得最大的关键字被放到最后的位置。例题如下5.快速排序（20分钟）快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。例题如下：三、课堂小结（5分钟）本次课我们了解了排序的基本概念，把一个无序的序列进行排序可以有效提高查找的效率，进而提高计算机运算速度。我们通过对四种排序方法的学习，基本掌握了排序的过程和思维，在解决实际问题时，又多了一种有

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论