高中数学有序列插入排序-备课资料.doc

用心爱心专心116号编辑有序列插入排序-备课资料学习导航学习提示1.通过具体实例学会把一个新的数据插入到已经排好顺序的数据列中使之仍是有序数据列.2.会反复用有序列插入排序算法把一个无序的数据列变成有序的数据列.3.了解折半插入排序方法.4.通过学习进一步体会算法思想并能应用它来解决某些具体问题.通过有序列插入排序的算法完成排序问题是本节的重点.互动学习知识链接1.在一次数学考试结束后的成绩统计中张磊考了85分排第15名王强考了82分排第16名.排完后老师发现张哲考了84分但没有给排进.事实上张哲应排第几名?另外孙明和石志伟在原来的排名中分别排第5名和第23名现在两人应分别排第几名?2.画出从三个数abc中找出最小的数的一个算法流程图.答案：1.张哲应排第16名孙明的排名不变仍排第5名而石志伟的排名应向后退一位排第24名.2.算法流程图如图2－3－1.图2－3－1反复进行两个数的大小比较是排序的重要方法.另外在解决问题的过程中顺序结构、选择结构、循环结构会被交互使用.课文知识点解析全析提示1.把一个新的数据插入到已经排好序的数据列中使之仍是有序数据列.例如一组从小到大排好顺序的数据列{135791113}我们常用序号123…表示数据的位置如序号4对应上面数列中的7.现在要把数据8插入到上述有序列中算法应该如何设计呢?主要考虑两个问题：一是要确定数据8在原有序列中怎样确定位置这里数据8应满足小于或等于原有序列中这个位置右边的数据大于其左边位置上的数据；二是确定数据8在这个有序列中的序号数据8左边的数据序号不变右边的数据序号都相应加1.其流程图如图2－3－2.图2－3－22.用有序列插入排序算法完成排序.问题的解决基本思想非常简单即反复使用有序列插入排序算法使有序列的长度不断增加一直到完成整个无序列的有序排列为止.如一无序列{a1a2a3…an}怎样进行插入排列呢?首先{a1}是有序列将a2插入有序列{a1}中得到新的有序列；再把a3插入到新的有序列中又得到一个新的有序列；……依次类推最后把无序列调整为有序列.3.折半插入排序法.这种算法的基本思想是先将新数据与数列中具有中间序号的那个数据进行比较如果与之相等则可确定其插入位置及序号；若不相等中间序号的数据将数据列分为两半当新数据较小时它的位置应在靠左的这一半否则在靠右的这一半中反复进行这种折半排序方法直到确定新数据的位置.在有序列中插入一个新的数据后有的数据的序列号可能要改变有的可能不变.要点提炼问题的想法往往非常简单要写出具体的算法就需要多练习、多体会、多总结.全析提示反复应用某种算法解决这类问题正好是循环结构的特长.全析提示折半插入排序与有序插入排序是两种不同的排序方法.同学们可以把它作为排序方法的补充了解它.