藍橋杯青少年創意編程大賽Scratch編程題解析（五）

列表排序

1.問題描述

老師給小貓出了一道題：在列表1中生成5個在1～99范圍內的隨機整數，然后按照從大到小的順序將它們依次移到列表2中。

例如：在列表1中隨機生成的整數依次是“12，3，1，13，17”，在處理之后列表2中的整數依次是“17，13，12，3，1”。如圖1、2。

具體要求：（1）每次點擊綠旗后，在屏幕中都顯示如圖1所示的列表1和列表2，且在列表1中隨機生成5個在1～99范圍內的隨機整數，而列表2中內容為空。然后小貓說“5秒鐘后開始處理”，并等待5秒鐘。

（2）處理數據時，每間隔1秒鐘，都將列表1中當前最大的一個數字移動到列表2中，注意：是移動，不是復制。

（3）當處理到列表1為空后，列表2中的數據應從大到小排列，如圖2所示，然后小貓說“處理完啦”2秒鐘，然后程序結束。

評判標準：10分，點擊綠旗后，在列表1中正確生成了5個隨機的整數（裁判可多次點擊綠旗來驗證是否隨機），且小貓說“5秒鐘后開始處理”，并等待5秒鐘。

30分，在10分標準的基礎上，開始處理后，每1秒鐘都將列表1中當前最大的數字移動到列表2中，但不是每次都移動最大數字或者移動到列表2中后順序不是從大到小，或者處理完成后小貓沒有說“處理完啦”，2秒鐘。

50分：完全符合題意。

2.編程思路

（1）隨機生成5個數字并存入列表1。

（2）找到當前列表1中的最大的數并存儲到列表2中，然后刪掉這個數，完成移動。

（3）重復執行第2步，直到列表1為空，結束循環。

（4）本題的難點是找到列表中最大的數。對列表排序的算法有很多種，本題數據量非常少，任何一種排序算法都是可以的。學習編程的小朋友可能都接觸過相對簡單的“冒泡排序算法”。標準的冒泡法是針對一個列表內排序，本題是兩個列表，需要做針對性的修改。

3.冒泡排序算法

我們來看看原版的算法步驟，這個步驟由于和題目要求有差異，只能借用，不能直接套用。

（1）需要降序排列，讓第一個數最大，最后一個數最小。

（2）比較相鄰的元素。如果第一個比第二個小，就交換它們兩個，保證大的數更靠前。

（3）對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。這樣最后的元素應該會是最小的數。

（4）針對所有的元素重復以上的步驟，除了最后一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

4.本題算法

冒泡法的核心是依次比較相鄰兩個數，并根據情況決定是否交換位置。

例如本題的列表“12，3，1，13，17”，建立一個“臨時”變量記錄列表的第一個數12，建立一個“臨時序號”記錄數據的序號1。依次與后面的數據比較，遇到3、1就不變，遇到13時“臨時”就替換為13，“臨時序號”變為4。一直對比到列表的末尾，這時“臨時”變量中記錄為17是列表1中最大的數值，“臨時序號”為5。這時將數據17放入列表2的第一個位置，并刪除列表中序號5的對應數值17。依次循環直到列表1中沒有數據為止。

算法流程圖如圖3。

5.編程實現

（1）對小貓編程，建立列表1、列表2。建立變量臨時、序號、臨時序號。清空列表。

（2）重復5次，將隨機數加入表1。如圖4。

（3）重復執行直到表1項目數為O。將序號、臨時序號設為1，將臨時設定為表1第1項。

（4）重復執行表1項目數-1次。如果表1（序號+1）項>臨時，將臨時替換為（序號+1）項，記錄臨時序號為（序號+1），將序號增加1。否則將序號增加1。此步驟完成時，臨時保存表1最大數，臨時序號記錄著它在表1的位置。

（5）將臨時加入表2，刪除表1的臨時序號項。根據題目要求等待1秒。

（6）說“處理完啦”2秒。程序如圖5。

6.解題思路B

本例中排序使用了臨時變量來存儲當前最大的數。下面提供另外一種解題思路，只使用2個變量，序號和最大項序號。比較第1項和第2項，如果第2項大于第1項，則將第2項作為最大項序號。接下來比較第2項和第3項，如果第2項大于第3項，則將序號加1，第2項繼續與第4項比較。比較到列表最后將最大項序號對應的值拷貝到表2中，并刪除。具體程序如圖6。