直接插入排序.ppt

徐洪章徐洪章8.2 8.2 直接插入排序直接插入排序数据结构数据结构计算机科学系计算机科学系n n教学内容：教学内容：1 1、排序的基本概念、排序的基本概念 2 2、直接插入排序算法的基本思想、直接插入排序算法的基本思想 3 3、直接插入排序算法实现、直接插入排序算法实现 4 4、直接插入排序算法性能分析、直接插入排序算法性能分析n n教学重点：教学重点：直接插入排序算法思想直接插入排序算法思想 n n教学难点：教学难点：算法实现及性能分析算法实现及性能分析 n n教学过程教学过程 学号学号姓名姓名学习成绩学习成绩 思想政治思想政治总分总分奖学金等次奖学金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX2312725831004XXX2112723838.2.1 排序概念排序概念排序排序无序无序数据数据有序有序数据数据排序算法主要有：排序算法主要有：排序算法主要有：排序算法主要有：直接插入排序直接插入排序直接插入排序直接插入排序、希尔排序、冒泡排序、快速排、希尔排序、冒泡排序、快速排、希尔排序、冒泡排序、快速排、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等。序、直接选择排序、堆排序、归并排序等。序、直接选择排序、堆排序、归并排序等。序、直接选择排序、堆排序、归并排序等。8.2.2 直接插入排序基本思想直接插入排序基本思想2121252549493616160808i n-1 数组下标数组下标数组数组R有序区有序区有序区有序区无序区无序区无序区无序区1313无序区第无序区第1 1个元素个元素0 i-1如何确定如何确定插入位置插入位置？关键问题关键问题212125254949363608081313排序过程排序过程临时变临时变量量temptemp165 54 43 32 20 01 1 n-1n-1下标下标流程图流程图(temp=0)(temp=0)开始开始temp=Ritemp=Rij=i-1j=i-1循环判断循环判断Rj+1=RjRj+1=Rjj-j-Rj=tempRj=tempN NY Y结束结束将无序区中的第一个元将无序区中的第一个元素放到临时变量中素放到临时变量中j j表示有序区中的最后表示有序区中的最后一个元素的位置一个元素的位置将当前元素向后移动将当前元素向后移动有序区中比较下一个有序区中比较下一个找到插入位置后将第找到插入位置后将第1 1个元素插入个元素插入8.2.3 算法实现算法实现for(i=1;in;i+)for(i=1;in;i+)for(i=1;in;i+)for(i=1;in;i+)/插入所有元素插入所有元素插入所有元素插入所有元素Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)int i,j,temp;int i,j,temp;int i,j,temp;int i,j,temp;temp=Ri;temp=Ri;temp=Ri;temp=Ri;/将待排序元素放入临时变量将待排序元素放入临时变量将待排序元素放入临时变量将待排序元素放入临时变量while(while(while(while(temp=0)(temp=0)(temp=0)(temp=0)Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;/元素向后移动元素向后移动元素向后移动元素向后移动 j-;j-;j-;j-;/向左继续查找向左继续查找向左继续查找向左继续查找 Rj+1=temp;Rj+1=temp;Rj+1=temp;Rj+1=temp;/将元素插入相应位置将元素插入相应位置将元素插入相应位置将元素插入相应位置 j=i-1;j=i-1;j=i-1;j=i-1;/从从Ri-1Ri-1开始向左查找开始向左查找 n n评价排序算法好坏的标准：评价排序算法好坏的标准：评价排序算法好坏的标准：评价排序算法好坏的标准：一、一、一、一、时间复杂度时间复杂度时间复杂度时间复杂度-算法执行所需要的时间算法执行所需要的时间算法执行所需要的时间算法执行所需要的时间(比较次数比较次数比较次数比较次数 和移动次数和移动次数和移动次数和移动次数)二、二、二、二、空间复杂度空间复杂度空间复杂度空间复杂度-算法执行所需要的辅助空间个数算法执行所需要的辅助空间个数算法执行所需要的辅助空间个数算法执行所需要的辅助空间个数主要考虑主要考虑次要考虑次要考虑for(i=1;in;i+)for(i=1;in;i+)for(i=1;in;i+)for(i=1;in;i+)Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)Void insertsort(arrayType R,int n)int i,j,temp;int i,j,temp;int i,j,temp;int i,j,temp;temp temp temp temp While(While(While(While()Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;j-;j-;j-;j-;Rj+1=;Rj+1=;Rj+1=;Rj+1=;j=i-1;j=i-1;j=i-1;j=i-1;=Ri;=Ri;=Ri;=Ri;R0 R0 R0 R0 2 2 2 2 R0 R0 R0 R0 temptemptemptemp(temp=0)(temp=0)(temp=0)(temp=0)R0RjR0RjR0RjR0Rj浪费时间浪费时间第一第一第一第一 进入循环之前，保存进入循环之前，保存进入循环之前，保存进入循环之前，保存RiRiRiRi的值的值的值的值第二第二第二第二 在在在在whilewhilewhilewhile循环中循环中循环中循环中“监视监视监视监视”下标下标下标下标 是否越界。是否越界。是否越界。是否越界。监视哨监视哨使用使用R0的意义的意义8.2.3 改进后改进后算法算法insertsort(R)insertsort(R)insertsort(R)insertsort(R)int i,j;int i,j;int i,j;int i,j;for(;in;i+)for(;in;i+)for(;in;i+)for(;in;i+)j=i-1;j=i-1;j=i-1;j=i-1;Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;Rj+1=Rj;j-;j-;j-;j-;R0R0R0R0=Ri;=Ri;=Ri;=Ri;whilewhilewhilewhile(R0Rj)(R0Rj)(R0Rj)(R0Rj)Rj+1=Rj+1=Rj+1=Rj+1=R0R0R0R0i=2i=2i=2i=28.2.4 性能分析性能分析21212525494936361616080813131 1、理想情况、理想情况2 2、最坏情况、最坏情况2121252549493636161608081313知识拓展知识拓展有没有更好有没有更好的方法来查的方法来查找插入位置找插入位置？简单、容易实现简单、容易实现效率不高效率不高查找插入位置的方法不当查找插入位置的方法不当本节小结本节小结谢谢 谢谢各位评委老师！各位评委老师！此课件下载可自行编辑修改，此课件供参考！此课件下载可自行编辑修改，此课件供参考！部分内容来源于网络，如有侵权请与我联系删除！部分内容来源于网络，如有侵权请与我联系删除！