《插入排序算法》教学课件

插入排序算法

排序算法设计插入排序算法算法原理训练项目程序设计算法评估教学目标教学目标掌握插入排序算法原理熟练控制类模板函数的返回值掌握利用for与while循环语句以多种方法编写插入排序函数的方法掌握根据实际需要对算法函数程序进行控制的方法插入排序算法教学目标训练项目程序设计算法评估算法原理

与选择排序算法不同，插入排序（InsertionSorting）是从无序部分不经选择，任取一元，然后插入到有序部分的正确位置。

关键在于我们能否改变循环结构并实现算法。该算法步骤如下：将L[1…n]分为两部分：L[1..i]为已排序部分，L[i+1…n]为未排序部分。（1）i=1

（2）把L[i+1…n]插入到L[1..i]中的正确位置，i++

（3）if(i<n)goto（2）（4）结束插入排序算法教学目标训练项目程序设计算法评估算法原理

程序分析：template<classType>TypeInsertSort(Types[],intn){ Typetemp;for(inti=1;i<=n-1;i++){ for(intj=i-1,temp=s[i];j>=0;j--){ if(s[j]>temp)s[j+1]=s[j]; else{s[j+1]=temp;break;k=0;} } } return*s;}

插入排序算法教学目标算法原理训练项目程序设计算法评估训练项目：

请同学们修正上述程序的错误，并进行完整的编程实践。插入排序算法教学目标算法概念动画演示程序设计算法评估设待排序数组为s[]其中，第i个元素为s[i]

第j个元素为s[j]fori=1,k=1J=i-1非零J>=0s[J+1]=s[J]非零零零v=s[i]i<=n-1s[J+1]=v;break;k=0;i++forJ=i-1s[J]>vJ--K==1s[J+1]=v零零非零非零插入排序算法教学目标算法概念动画演示程序设计算法评估了解插入排序算法函数template<classType>TypeInsertSort(Types[],intn){ Typetemp;intk;for(inti=1;i<=n-1;i++){ k=1;for(intj=i-1,temp=s[i];j>=0;j--){ if(s[j]>temp)s[j+1]=s[j]; else{s[j+1]=temp;break;k=0;} } if(k==1)s[j+1]=temp;} return*s;}

插入排序算法教学目标算法概念动画演示程序设计算法评估

编程实操请同学们，根据插入排序算法函数的原理，并增加输入输出功能，编写完成的算法程序。

插入排序算法教学目标算法概念动画演示程序设计算法评估插入排序算法与选择排序算法都有两重循环，但却有一个重要的差别，就是在选择排序算法中，内层循环次数是确定的，而在插入排序算法中，内层循环次数是不确定的，因此，其最坏情形和平均情形的时间复杂度是不同的。显然，插入排序最坏情形出现在内层循环中，变量j的值都是从i-1变到0。例如，当L[1…n]的元素值不同且恰为降序排列时，最坏情形出现，

W(n)=插入排序的最好情形，显然是内层循环每次只进行一次比较。例如当L[1…n]的元素值本身就是按升序排列时，B(n)=n-1插入排序算法教学目标算法概念问题长度程序设计算法评估

作业1请使用两种不同的插入排序算法程序