《直接插入排序》PPT课件.ppt
《《直接插入排序》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《直接插入排序》PPT课件.ppt(19页珍藏版)》请在三一办公上搜索。
1、徐洪章,8.2 直接插入排序,数据结构,计算机科学系,教学内容:1、排序的基本概念 2、直接插入排序算法的基本思想 3、直接插入排序算法实现 4、直接插入排序算法性能分析,教学重点:直接插入排序算法思想,教学难点:算法实现及性能分析,教学过程,8.2.1 排序概念,排序,无序数据,有序数据,排序算法主要有:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等。,8.2.2 直接插入排序基本思想,21,25,49,36,16,08,i n-1 数组下标,数组R,有序区,无序区,13,无序区第1个元素,0 i-1,如何确定插入位置?,关键问题,21,25,49,36,08,
2、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+)/插入所有元素,Void insertsort(arrayType R,int n)int i,j,temp;,temp=Ri;/将待排序元素放入临时变量,while(temp=0)Rj+1=Rj;/元素
3、向后移动 j-;/向左继续查找,Rj+1=temp;/将元素插入相应位置,j=i-1;/从Ri-1开始向左查找,评价排序算法好坏的标准:,一、时间复杂度-算法执行所需要的时间(比较次数 和移动次数),二、空间复杂度-算法执行所需要的辅助空间个数,主要考虑,次要考虑,for(i=1;in;i+),Void insertsort(arrayType R,int n)int i,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)int i,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,知识拓展,有没有更好的方法来查找插入位置?,简单、容易实现,效率不高,查找插入位置的方法不当,本节小结,谢 谢各位评委老师!,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 直接插入排序 直接 插入 排序 PPT 课件

链接地址:https://www.31ppt.com/p-5587429.html