Question

1．期中考試結(jié)束了，班長給學(xué)生按學(xué)分排隊(duì)，一個(gè)小組原有六人，由于某小組組長的疏忽，把一個(gè)同學(xué)的學(xué)分遺漏了，現(xiàn)要把該學(xué)分插進(jìn)去應(yīng)怎么辦？

設(shè)排好的學(xué)分為有序列{1，3，6，7，9}，該同學(xué)的學(xué)分為5分．同學(xué)們可以想象一下，假如學(xué)分順序已經(jīng)排好，恰好剩你一個(gè)人，怎么辦？

2．若將上述例題中學(xué)生的學(xué)分順序打亂，然后按從小到大的順序排序，該如何做？不妨設(shè)亂序?yàn)閧7，3，6，9，1}．

Answer 1

答案：
解析：

1．解法一：將5從右向左逐個(gè)與有序列中的數(shù)據(jù)進(jìn)行比較，確定5在序列中的位置，并將其插入構(gòu)成一個(gè)新的有序列，這個(gè)過程可以用下列步驟描述： 　　(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}，構(gòu)成一個(gè)新的有序列． 　　首先選擇有序列的“中間位置”的數(shù)據(jù)a3＝6，將5與a3比較，顯然5＜a3，所以5應(yīng)排在a3的左邊．如果還沒有確定位置應(yīng)再取余下數(shù)據(jù)列的“中間位置”的數(shù)據(jù)比較查找． 　　感悟：(1)有序直接插入法中的“比較法”：將數(shù)據(jù)A與原有序列中的數(shù)據(jù)從右向左依次進(jìn)行比較，直到發(fā)現(xiàn)某一數(shù)據(jù)ai，使得ai≤A，把A插入到ai的右邊；如果數(shù)據(jù)A小于原有序列中的所有數(shù)據(jù)，則將A插入到原有序列的最左邊． 　　(2)折半插入法中的“二分法”：用折半插入排序法向有序列中插入新數(shù)據(jù)時(shí)，首先應(yīng)確定原有序列中數(shù)據(jù)的個(gè)數(shù)是偶數(shù)2n還是奇數(shù)2n＋1．若為偶數(shù)，則“中間位置”的數(shù)據(jù)是第n個(gè)數(shù)；若為奇數(shù)，則“中間位置”的數(shù)據(jù)為第n＋1個(gè)數(shù)，然后用新數(shù)據(jù)與“中間位置”的數(shù)據(jù)比較，若新數(shù)據(jù)大于“中間位置”的數(shù)據(jù)，則在右半邊進(jìn)行下一步；若新數(shù)據(jù)小于“中間位置”的數(shù)據(jù)，則在左半邊進(jìn)行下一步；若新數(shù)據(jù)等于“中間位置”的數(shù)據(jù)，則將新數(shù)據(jù)插入到“中間位置”的數(shù)據(jù)的右邊，依次類推，就可以確定新數(shù)據(jù)在有序列中的位置，這是二分法的具體應(yīng)用． 　　以上是在已經(jīng)排好的有序列中插入一個(gè)新數(shù)據(jù)，但是生活中肯定會面臨無序的數(shù)字串排序的問題，這種問題該怎么辦？ 　　2．解法一：算法步驟為： 　　(1)只有一個(gè)數(shù)的序列{7}是有序列； 　　(2)將3插入有序數(shù)列{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}． 　　所以有序數(shù)列為{1，3，6，7，9}． 　　解法二：算法步驟為： 　　(1)在序列{7，3，6，9，1}中選出最小的數(shù)據(jù)1放在第1個(gè)位置上； 　　(2)在序列{7，3，6，9}中選出最小數(shù)3放在第2位； 　　(3)在序列{7，6，9}中選出最小數(shù)6放在第3位； 　　(4)在序列{7，9}中選出最小數(shù)7放在第4位； 　　(5)將9排在第5位． 　　感悟：解法一中，第一個(gè)數(shù)據(jù)的選取，沒有什么要求，只需按逐一比較排序；解法二中的第1步需選所有數(shù)據(jù)中的最小數(shù)作為基準(zhǔn)，依次找最小數(shù)排序．體會兩者的算法思想，學(xué)會處理問題的思維方法． 　　總之，解決排序插入問題，應(yīng)先判斷所給題目是否有序，若有序用題1所用的兩種思維方法排序，若無序可用題2所用的兩種思維方法排序，這些都屬于簡單的排序問題，也是算法思想的具體應(yīng)用．