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