北师大版高中数学必修三2.1.2排序问题与算法的多样性 教案

第二课时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
五、教学反思：