高中数学有序列插入排序-典型例题北师大版教材必修三.doc

用心爱心专心

有序列插入排序-典型例题规律发现【例1】已知一组有序列{13，27，38，39，43，47，48，51，57，66，74，82}，现要将数据52插入到数据列中.
（1）请设计算法，确定数据52在数据列中位置的序号，并画出算法示意图；
（2）在确定了52位置序号的前提下，请设计算法将数据52插入有序列；
（3）请用流程图描述整个插入过程的算法.
分析：首先应该设置变量，且由于多次重复比较算法，宜选用循环结构.
解：（1）引入变量i表示数据位置的序号，变量R［i］表示数据序号为i的数据，即R［1］：=13，R［2］：=27，R［3］：=38，R［4］：=39，…，R［12］：=82.将52从右向左逐个与有序列中的数据进行比较，确定52应占位置的序号.其算法示意图如图2－3－3.
比较52与R［12］的大小，由52<R［12］↓
比较52与R［11］的大小，由52<R［11］↓
比较52与R［10］的大小，由52<R［10］↓
比较52与R［9］的大小，由52<R［9］↓
比较52与R［8］的大小，由52>R［8］↓
则数据52的序号为9图2－3－3
（2）当52的位置序号确定后，接下来要增加一个序号13，同时增加一个变量R［13］，同时，由于52放在了序号为9的位置，因此，原序号为9～12的数据，依次向右移动一位，且序号都加上1.其算法为：
①R［13］：=R［12］，②R［12］：=R［11］，
③R［11］：=R［10］，④R［10］：=R［9］，
⑤R［9］：=52.结束.
（3）在插入排序过程中，以上两步要同时进行，因此其算法流程图为

图2－3－4
【例2】有无序列{a1，a2，…，an}，将其按从小到大的顺序排列，画出算法流程图.
分析：可以从左到右，依次执行有序列插入排序算法.
解：算法流程图如图2－3－5.

图2－3－5先写出算法示意图，有助于写算法流程图.

在算法中要把各个数据赋予相应的变量，有助于具体算法的处理.

插入数据52后，有些数据的序号要随之改变，在算法中可以体现出这一点.

两步同时进行的含义是在比较的过程中，边比较，边完成插入赋值.

根据题目要求，设置两级循环结构，使排序由少到多.此流程图具有一般意义.