直接插入排序

关于直接插入排序第1页，课件共19页，创作于2023年2月教学内容：

1、排序的基本概念

2、直接插入排序算法的基本思想

3、直接插入排序算法实现

4、直接插入排序算法性能分析教学重点：直接插入排序算法思想

教学难点：算法实现及性能分析

教学过程

第2页，课件共19页，创作于2023年2月第3页，课件共19页，创作于2023年2月学号姓名学习成绩思想政治总分奖学金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX2312725831004XXX211272383………………第4页，课件共19页，创作于2023年2月8.2.1排序概念排序无序数据有序数据排序算法主要有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序等。第5页，课件共19页，创作于2023年2月8.2.2直接插入排序基本思想212549361608i…n-1数组下标数组R有序区无序区13无序区第1个元素……0…

i-1第6页，课件共19页，创作于2023年2月如何确定插入位置？关键问题第7页，课件共19页，创作于2023年2月212549360813排序过程临时变量temp16543201…n-1下标…第8页，课件共19页，创作于2023年2月流程图(temp<R[j])&&(j>=0)开始temp=R[i]j=i-1循环判断R[j+1]=R[j]j--R[j]=tempNY结束将无序区中的第一个元素放到临时变量中j表示有序区中的最后一个元素的位置将当前元素向后移动有序区中比较下一个找到插入位置后将第1个元素插入第9页，课件共19页，创作于2023年2月8.2.3算法实现for(i=1;i<n;i++){//插入所有元素Voidinsertsort(arrayTypeR[],intn){inti,j,temp;temp=R[i];//将待排序元素放入临时变量while((temp<R[j])&&(j>=0)){R[j+1]=R[j];//元素向后移动j--;//向左继续查找

}R[j+1]=temp;//将元素插入相应位置

}j=i-1;//从R[i-1]开始向左查找}第10页，课件共19页，创作于2023年2月评价排序算法好坏的标准：一、时间复杂度-算法执行所需要的时间(比较次数和移动次数)二、空间复杂度-算法执行所需要的辅助空间个数主要考虑次要考虑第11页，课件共19页，创作于2023年2月for(i=1;i<n;i++){Voidinsertsort(arrayTypeR[],intn){inti,j,temp;tempWhile(

){R[j+1]=R[j];j--;}R[j+1]=;}j=i-1;}=R[i];R[0]2R[0]temp(temp<R[j])&&(j>=0)R[0]<R[j]浪费时间第12页，课件共19页，创作于2023年2月第一进入循环之前，保存R[i]的值第二在while循环中“监视”下标是否越界。监视哨使用R[0]的意义第13页，课件共19页，创作于2023年2月8.2.3改进后算法insertsort(R){inti,j;for(;i<n;i++){

j=i-1;

{R[j+1]=R[j];j--;}

;}}

R[0]=R[i];while(R[0]<R[j])R[j+1]=R[0]i=2第14页，课件共19页，创作于2023年2月8.2.4性能分析212549361608131、理想情况第15页，课件共19页，创作于2023年2月2、最坏情况21254936160813第16页，课件共19页，创作于2023年2月知识拓展有没有更好的方法来查找