第四课时 2.3 排序问题学习重点：有序列插入排序方法和折半插入排序方法的原理与过程。学习难点：用算法语句描述排序方法。学习目标：1. 理解有序列插入排序方法和折半插入排序，并会设计算法2.通过实例，发展用有序列插入排序方法和折半插入排序解决问题的能力。学习过程：为了便于查询，常常需要根据要求将被查寻的对象按 照一定的顺序排列，通常称为排序。例如：新来的同学小黄身高 175cm，在班上是中等身高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？象这样在已经按一定顺序排好的系列（有序列）中插入一个数据，我们就叫它有序列插入排序。 有序列直接插入排序法有序列直接插入排序：用有序列直接插入排序 算法完成无序列排序问题，其基本思想非常简单，即反复使用有序列直接插入排序算法，使有序列的长度不断增加，一直到完成整个无序列的有序排列为止．一般地，对于一个有序列：a1≤a2≤a3≤…≤an，欲将新数据 A 插入到有序列中，形成新的有序列，其做法是：将数据 A 与原有序列中的数据从右到左依次进行 比较，直到发现某一数据 ai，使得 ai≤A，把 A 插入到 ai 的右边；如果数据 A 小于原有序列中的所有数据，则将 A 插入到原序列的最左边．上面的排序算法通常称为有序列直接插入排序的算法．我们在一个已经排好顺序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。例如：要将 8 插入到{1,3,5,7,9,11,13}中，我们怎样考虑？首先确定 8 在原系列中的位置，使 8 小于或等于原系列中右边的数据，大于或等于左边的数据，将这个位置空出来，将数据 8 插进去例题分析：例 1 已知有一组系列{13,27,38,39,43,47,48,51,57,66,74}，现要将数据 52 插入到数据中。数据序列号12345678910111357891113原序列1327383943474851576674(1)请设计算法，确定 52 在新数据中的位置。(2)在确定 52 的序列号后，请将 52 插入系列中(3)请用流程图描述这个插入过程的算法问题思考:对于一组无序的数据列{49,38,65,97,76,13,27,49}如何完 成排序工作呢?折半插入排序如果 R[1..i-1] 是一个按关键字有序 的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找 R[i]的插入位置”，如此实现的插入排序为折半插入排序。折半插入排序性能分析1）折半插入排序所需附加存储空间和直接插入排序相同，从时间上来看，折半插入排序减少了关键字的比较次数，但是移动次数不变。2）折...
