直接插入排序幻灯片_第1页
直接插入排序幻灯片_第2页
直接插入排序幻灯片_第3页
直接插入排序幻灯片_第4页
直接插入排序幻灯片_第5页
已阅读5页，还剩14页未读， 继续免费阅读

下载本文档

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

文档简介

徐洪章,8.2直接插入排序,数据结构,计算机科学系,教学内容：1、排序的基本概念2、直接插入排序算法的基本思想3、直接插入排序算法实现4、直接插入排序算法性能分析,教学重点：直接插入排序算法思想,教学难点：算法实现及性能分析,教学过程,8.2.1排序概念,排序,无序数据,有序数据,排序算法主要有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等。,8.2.2直接插入排序基本思想,21,25,49,36,16,08,in-1数组下标,数组R,有序区,无序区,13,无序区第1个元素,0i-1,如何确定插入位置？,关键问题,21,25,49,36,08,13,排序过程,临时变量temp,16,5,4,3,2,0,1,n-1,下标,流程图,(temp=0),开始,temp=Ri,j=i-1,循环判断,Rj+1=Rj,j-,Rj=temp,N,Y,结束,将无序区中的第一个元素放到临时变量中,j表示有序区中的最后一个元素的位置,将当前元素向后移动,有序区中比较下一个,找到插入位置后将第1个元素插入,8.2.3算法实现,for(i=1;in;i+)/插入所有元素,Voidinsertsort(arrayTypeR,intn)inti,j,temp;,temp=Ri;/将待排序元素放入临时变量,while(temp=0)Rj+1=Rj;/元素向后移动j-;/向左继续查找,Rj+1=temp;/将元素插入相应位置,j=i-1;/从Ri-1开始向左查找,评价排序算法好坏的标准：,一、时间复杂度-算法执行所需要的时间(比较次数和移动次数),二、空间复杂度-算法执行所需要的辅助空间个数,主要考虑,次要考虑,for(i=1;in;i+),Voidinsertsort(arrayTypeR,intn)inti,j,temp;,temp,While()Rj+1=Rj;j-;,Rj+1=;,j=i-1;,=Ri;,R0,2,R0,temp,(temp=0),R0Rj,浪费时间,第一进入循环之前，保存Ri的值,第二在while循环中“监视”下标是否越界。,监视哨,使用R0的意义,8.2.3改进后算法,insertsort(R)inti,j;for(;in;i+)j=i-1;Rj+1=Rj;j-;,R0=Ri;,while(R0Rj),Rj+1=R0,i=2,8.2.4性能分析,21,25,49,36,16,08,13,1、理想情况,2、最坏情况,21,25,49,36,16,08,13,知识拓展,有
人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

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

最新文档

评论

0/150

提交评论