资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
徐洪章,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,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; /元素向后移动 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,知识拓展,有没有更好的方法来查找插入位置?,简单、容易实现,效率不高,查找插入位置的方法不当,本节小结,谢 谢 各位评委老师!,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号