1．期中考试结束了，班长给学生按学分排队，一个小组原有六人，由于某小组组长的疏忽，把一个同学的学分遗漏了，现要把该学分插进去应怎么办？设排好的学分为有序列{1，3，6，

Question

1．期中考试结束了，班长给学生按学分排队，一个小组原有六人，由于某小组组长的疏忽，把一个同学的学分遗漏了，现要把该学分插进去应怎么办？

设排好的学分为有序列{1，3，6，7，9}，该同学的学分为5分．同学们可以想象一下，假如学分顺序已经排好，恰好剩你一个人，怎么办？

2．若将上述例题中学生的学分顺序打乱，然后按从小到大的顺序排序，该如何做？不妨设乱序为{7，3，6，9，1}．

Answer 1

　　1．解法一：将5从右向左逐个与有序列中的数据进行比较，确定5在序列中的位置，并将其插入构成一个新的有序列，这个过程可以用下列步骤描述：

　　(1)比较5与9，5＜9；

　　(2)比较5与7，5＜7；

　　(3)比较5与6，5＜6；

　　(4)比较5与3，5＞3；

　　(5)将5插到3与6之间得到新的有序列：{1，3，5，6，7，9}．

　　解法二：要将5插入有序列{1，3，6，7，9}，构成一个新的有序列．

　　首先选择有序列的“中间位置”的数据a₃＝6，将5与a₃比较，显然5＜a₃，所以5应排在a₃的左边．如果还没有确定位置应再取余下数据列的“中间位置”的数据比较查找．

　　感悟：(1)有序直接插入法中的“比较法”：将数据A与原有序列中的数据从右向左依次进行比较，直到发现某一数据ai，使得ai≤A，把A插入到ai的右边；如果数据A小于原有序列中的所有数据，则将A插入到原有序列的最左边．

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

　　以上是在已经排好的有序列中插入一个新数据，但是生活中肯定会面临无序的数字串排序的问题，这种问题该怎么办？

　　2．解法一：算法步骤为：

　　(1)只有一个数的序列{7}是有序列；

　　(2)将3插入有序数列{7}中，得到新序列：{3，7}；

　　(3)将6插入有序列{3，7}中，得到新序列：{3，6，7}；

　　(4)将9插入有序列{3，6，7}中，得到新序列：{3，6，7，9}；

　　(5)将1插入有序列{3，6，7，9}中，得到新序列：{1，3，6，7，9}．

　　所以有序数列为{1，3，6，7，9}．

　　解法二：算法步骤为：

　　(1)在序列{7，3，6，9，1}中选出最小的数据1放在第1个位置上；

　　(2)在序列{7，3，6，9}中选出最小数3放在第2位；

　　(3)在序列{7，6，9}中选出最小数6放在第3位；

　　(4)在序列{7，9}中选出最小数7放在第4位；

　　(5)将9排在第5位．

　　感悟：解法一中，第一个数据的选取，没有什么要求，只需按逐一比较排序；解法二中的第1步需选所有数据中的最小数作为基准，依次找最小数排序．体会两者的算法思想，学会处理问题的思维方法．

　　总之，解决排序插入问题，应先判断所给题目是否有序，若有序用题1所用的两种思维方法排序，若无序可用题2所用的两种思维方法排序，这些都属于简单的排序问题，也是算法思想的具体应用．