2019-2020年高中数学 第二章 算法初步 3.2 循环语句教学案 北师大版必修3

S3 因为3>1，输出1,3,5； S4 因为6>5，输出1,3,5,6.

专题六折半插入排序法

折半插入排序：折半插入排序的基本思想是先将新数据与有序列中“中间位置”的那个数据进行比较，如果与之相等，则可确定其插入位置及序号；若不相等，中间位置的数据将数据列分为两半，当新数据较小时，它的位置应在靠左的一半，否则在靠右的一半．反复进行这种查找的方法，直到确定新数据的位置．通过前面的研究我们知道，折半插入排序方法中应用了二分法的思想后，少了多次无用的比较．相比较前面的有序列直接插入排序算法，会减少一些资源的浪费．对折半插入排序的理解：

先将新数据与有序列中“中间位置”的数据进行比较，若有序列有2n＋1个数据，则“中间位置”的数据指的是第n＋1个数据，若有2n个数据，则“中间位置”的数据指的是第n个数据，如果新数据小于中间位置的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于中间位置的数据，则将新数据插入到中间位置的数据的右边；如果新数据大于中间位置的数据，则新数据插入的位置应该在靠右边的一半．也就是说，一次比较就排除了数据中一半的位置．反复进行这种比较，直到确定新数据的位置．

例七将52插入有序列{13,27,38,39,43,47,48,51,57,66,74,82}中，构成一个新的有序列．

[解] 首先选择有序列中具有中间位置序号的数据47，将52与47进行比较，显然52>47，故52不能插入到47的左边的任何位置．所以，应该排在47的右边，再将余下数据的中间位置的数据57与52比较，显然52<57，因此应插到57的左边，又51<52，则52插入到51的右边，57的左边，即可得到52的位置．

评析：用折半插入排序法向有序列中插入新数据时，首先确定原有序列中数据的个数是偶数2n还是奇数2n＋1.若为偶数，则“中间位置”的数据是第n个数据；若为奇数，则“中间位置”的数据为第n＋1个数据，然后将新数据与“中间位置”的数据比较，若新数据大于“中间位置”的数据，则在右半边进行下一步骤；若新数据小于“中间位置”的数据，则在左半边进行下一步骤；依次类推，就可以确定新数据在序列中的位置．