直接插入排序

1、关于直接插入排序第一张，PPT共十九页，创作于2022年6月教学内容： 1、排序的基本概念 2、直接插入排序算法的基本思想 3、直接插入排序算法实现 4、直接插入排序算法性能分析教学重点：直接插入排序算法思想 教学难点：算法实现及性能分析 教学过程 第二张，PPT共十九页，创作于2022年6月第三张，PPT共十九页，创作于2022年6月学号姓名学习成绩思想政治总分奖学金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX231272583

2、1004XXX211272383第四张，PPT共十九页，创作于2022年6月8.2.1 排序概念排序无序数据有序数据排序算法主要有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等。第五张，PPT共十九页，创作于2022年6月8.2.2 直接插入排序基本思想212549361608i n-1 数组下标数组R有序区无序区13无序区第1个元素0 i-1第六张，PPT共十九页，创作于2022年6月如何确定插入位置？关键问题第七张，PPT共十九页，创作于2022年6月212549360813排序过程临时变量temp16543201n-1下标第八张，PPT共十九页，创作于20

3、22年6月流程图(temp=0)开始temp=Rij=i-1循环判断Rj+1=Rjj-Rj=tempNY结束将无序区中的第一个元素放到临时变量中j表示有序区中的最后一个元素的位置将当前元素向后移动有序区中比较下一个找到插入位置后将第1个元素插入第九张，PPT共十九页，创作于2022年6月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;

4、 /将元素插入相应位置 j=i-1; /从Ri-1开始向左查找第十张，PPT共十九页，创作于2022年6月评价排序算法好坏的标准：一、时间复杂度- 算法执行所需要的时间(比较次数 和移动次数)二、空间复杂度- 算法执行所需要的辅助空间个数主要考虑次要考虑第十一张，PPT共十九页，创作于2022年6月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浪费时间第十二张，PPT共十九页，

5、创作于2022年6月第一 进入循环之前，保存Ri的值第二 在while循环中“监视”下标 是否越界。监视哨使用R0的意义第十三张，PPT共十九页，创作于2022年6月8.2.3 改进后算法insertsort(R)int i,j;for ( ;in;i+) j=i-1; Rj+1=Rj; j-; ; R0=Ri;while(R0Rj)Rj+1=R0i=2第十四张，PPT共十九页，创作于2022年6月8.2.4 性能分析212549361608131、理想情况第十五张，PPT共十九页，创作于2022年6月2、最坏情况21254936160813第十六张，PPT共十九页，创作于2022年6月知识拓展有没有更好的方法来查找插入位置？简单、容易实现效率不高查找插入位置的方法不