徐洪章,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,知识拓展,有没有更好的方法来查找插入位置？,简单、容易实现,效率不高,查找插入位置的方法不当,本节小结,谢 谢 各位评委老师！,