第二课时2.1．2排序问题与算法的多样性 一、教学目标：通过对具体实例的解决过程与步骤的分析，了解排序问题。 二、教学重难点：1、有序列的直接插入排序；2、算法设计和算法流程图。 三、教学方法：探究讨论，思考交流。 四、教学过程 （一）、创设情景，导入新课 在如常生活中，人们经常要查询信息，例如，在词典中查找某个词的读音或含义，在图书馆里根据作者或者书名查找书目，在电话薄中查找某单位或某人的电话号码等。 为了便于查询和检索，我们常常根据某种要求把被查询的对象用数字（或者符号）表示出来，并把数字按大小排列，是信息处理中一项基本的工作。通常称为排序。排序的算法很多，这里给大家介绍一些经常使用的排序方法。 （二）、探究新知 1、有序列的概念： 对于一组数据按照一定的规则顺序排列时，通常称之为有序列. 2、有序列插入排序 问题提出：新来的同学小黄升高1.75cm，在班上是中等身高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？ 象这样一种在已经按一定顺序排好的系列（有系列）中插入，我们就叫它有序列插入排序 有序列插入排序：在已经按照某一规则排好的一系列数中，再插进一个数，成为新的一序列数，且仍按照原来的规则排列. 要将8插入到{1,3,5,7,9,11,13}中，我们怎样考虑？ 确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据，将这个位置空出来，将数据8插进去 1 3 5 7 ?8 9 11 13 练习：1、用直接插入法把23插入有序列5 8 11 24 33 38 45 48 50 60中，则23在该有序列中的序位为（ ） 2、用直接插入法把95插入有序列45 55 67 81 99 102 105 152中，则该有序列中的第1个数和最后一个数的序号变为（ ） 答案C A.1 8 B. 2 9 C. 1 9 D.2 8 问题一：已知一有序数组{38，39，51，57，66}，现在要将数据52插入到数据列中. 分析：1、从数组的序号入 序号 1 2 3 4 5 数组 38 39 51 57 66 2、创建新的序号，比较数的大小移动数 旧序号 1 2 3 4 5 旧数组 38 39 51 57 66 新序号 1 2 3 4 5 6 新数组 38 39 51 流程图： 问题二：对一个有序列{ R[1],R[2],…,R[n] }，要将新数据A插入到有序列中，形成新的有序列， 应该怎么做呢？根据分析原理画出流程 思考：1、还有其它插入A的方法吗？画出流程2、如何以有序排列的算法为平台进行无序排 { 49,38,65,97,76,13,27,49} 3、有序列插入排序算法的另一种方法折半插入排序法。请同学们参看P84.下段 问题思考:对于一组无序的数据列{49,38,65,97,76,13,27,49}如何完 成排序工作呢?请同学们参看P85 （1）折半插入排序：如果R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。 （2）、折半插入排序性能分析：1）折半插入排序所需附加存储空间和直接插入排序相同，从时间上来看，折半插入排序减少了关键字的比较次数，但是移动次数不变。2）折半插入排序的时间复杂度为o(n2)。3）折半插入排序是一个稳定的排序方法。 （3）、折半插入排序： （三）、小结：本次课主要介绍了：1.有关排序的基础知识（1）．定义（2）．稳定性和存储方式（3）．排序算法的评价 2.直接插入排序 3、折半插入排序 （1）．基本思想 （2）．实例模拟（3）．算法描述（4）．算法的复杂度。 （四）、作业布置：课本习题2-1A组8、9 五、教学反思： ... ...
~~ 您好，已阅读到文档的结尾了 ~~
