货物选取软件设计情境_插入排序算法程序单元(2).ppt

货物选取软件设计情境 插入排序算法程序单元 2 货物选取软件设计情境 插入排序算法程序单元 2 算法原理 训练项目 程序设计 算法评估 教学目标 教学目标进一步掌握插入排序算法原理熟练控制类模板函数的返回值掌握利用for与while循环语句以多种方法编写插入排序函数的方法掌握根据实际需要对算法函数程序进行控制的方法 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 训练项目 程序设计 算法评估 算法原理 与选择排序算法不同 插入排序 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 结束 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 训练项目 程序设计 算法评估 算法原理 程序分析 templateTypeInsertSort Types intn Typetemp for inti 1 i 0 j if s j temp s j 1 s j else s j 1 temp break k 0 return s 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法原理 训练项目 程序设计 算法评估 训练项目 请同学们修正上述程序的错误 并进行完整的编程实践 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法概念 动画演示 程序设计 算法评估 设待排序数组为s 其中 第i个元素为s i 第j个元素为s j 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法概念 动画演示 程序设计 算法评估 了解插入排序算法函数templateTypeInsertSort Types intn Typetemp intk for inti 1 i 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 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法概念 动画演示 程序设计 算法评估 编程实操请同学们 根据插入排序算法函数的原理 并增加输入输出功能 编写完成的算法程序 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法概念 动画演示 程序设计 算法评估 插入排序算法与选择排序算法都有两重循环 但却有一个重要的差别 就是在选择排序算法中 内层循环次数是确定的 而在插入排序算法中 内层循环次数是不确定的 因此 其最坏情形和平均情形的时间复杂度是不同的 显然 插入排序最坏情形出现在内层循环中 变量j的值都是从i 1变到0 例如 当L 1 n 的元素值不同且恰为降序排列时 最坏情形出现 W n 插入排序的最好情形 显然是内层循环每次只进行一次比较 例如当L 1 n 的元素值本身就是按升序排列时 B n n 1 货物选取软件设计情境 插入排序算法程序单元 2 教学目标 算法概念 问题长度 程序设计 算法评估 作业1请使用两种不同的插入排序算法程序完成实践项目 设数组为某空港物流中心若干种货物单个包装重