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}，構成一個新的有序列． 　　首先選擇有序列的“中間位置”的數據a3＝6，將5與a3比較，顯然5＜a3，所以5應排在a3的左邊．如果還沒有確定位置應再取余下數據列的“中間位置”的數據比較查找． 　　感悟：(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所用的兩種思維方法排序，這些都屬于簡單的排序問題，也是算法思想的具體應用．