直接插入排序幻灯片.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,徐洪章,8.2,直接插入排序,数据结构,计算机科学系,教学内容：,1,、排序的基本概念,2,、直接插入排序算法的基本思想,3,、直接插入排序算法实现,4,、直接插入排序算法性能分析,教学重点：,直接插入排序算法思想,教学难点：,算法实现及性能分析,教学过程,学号,姓名,学习成绩,思想政治,总分,奖学金等次,1008,XXX,262,29,291,1,1005,XXX,250,29,279,2,1003,XXX,249,28,277,2,1002,XXX,248,28,276,2,1006,XXX,243,28,271,3,1007,XXX,242,27,269,3,1001,XXX,231,27,258,3,1004,XXX,211,27,238,3,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,知识拓展,有没有更好的方法来查找插入位置？,简单、容易实现,效率不高,查找插入位置的方法不当,本节小结,谢 谢,各位评委老师！,