藍(lán)橋杯青少年創(chuàng)意編程大賽Scratch編程題解析（五）

列表排序

1.問(wèn)題描述

老師給小貓出了一道題：在列表1中生成5個(gè)在1～99范圍內(nèi)的隨機(jī)整數(shù)，然后按照從大到小的順序?qū)⑺鼈円来我频搅斜?中。

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

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

（2）處理數(shù)據(jù)時(shí)，每間隔1秒鐘，都將列表1中當(dāng)前最大的一個(gè)數(shù)字移動(dòng)到列表2中，注意：是移動(dòng)，不是復(fù)制。

（3）當(dāng)處理到列表1為空后，列表2中的數(shù)據(jù)應(yīng)從大到小排列，如圖2所示，然后小貓說(shuō)“處理完啦”2秒鐘，然后程序結(jié)束。

評(píng)判標(biāo)準(zhǔn)：10分，點(diǎn)擊綠旗后，在列表1中正確生成了5個(gè)隨機(jī)的整數(shù)（裁判可多次點(diǎn)擊綠旗來(lái)驗(yàn)證是否隨機(jī)），且小貓說(shuō)“5秒鐘后開始處理”，并等待5秒鐘。

30分，在10分標(biāo)準(zhǔn)的基礎(chǔ)上，開始處理后，每1秒鐘都將列表1中當(dāng)前最大的數(shù)字移動(dòng)到列表2中，但不是每次都移動(dòng)最大數(shù)字或者移動(dòng)到列表2中后順序不是從大到小，或者處理完成后小貓沒(méi)有說(shuō)“處理完啦”，2秒鐘。

50分：完全符合題意。

2.編程思路

（1）隨機(jī)生成5個(gè)數(shù)字并存入列表1。

（2）找到當(dāng)前列表1中的最大的數(shù)并存儲(chǔ)到列表2中，然后刪掉這個(gè)數(shù)，完成移動(dòng)。

（3）重復(fù)執(zhí)行第2步，直到列表1為空，結(jié)束循環(huán)。

（4）本題的難點(diǎn)是找到列表中最大的數(shù)。對(duì)列表排序的算法有很多種，本題數(shù)據(jù)量非常少，任何一種排序算法都是可以的。學(xué)習(xí)編程的小朋友可能都接觸過(guò)相對(duì)簡(jiǎn)單的“冒泡排序算法”。標(biāo)準(zhǔn)的冒泡法是針對(duì)一個(gè)列表內(nèi)排序，本題是兩個(gè)列表，需要做針對(duì)性的修改。

3.冒泡排序算法

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

（1）需要降序排列，讓第一個(gè)數(shù)最大，最后一個(gè)數(shù)最小。

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

（3）對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這樣最后的元素應(yīng)該會(huì)是最小的數(shù)。

（4）針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

4.本題算法

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

例如本題的列表“12，3，1，13，17”，建立一個(gè)“臨時(shí)”變量記錄列表的第一個(gè)數(shù)12，建立一個(gè)“臨時(shí)序號(hào)”記錄數(shù)據(jù)的序號(hào)1。依次與后面的數(shù)據(jù)比較，遇到3、1就不變，遇到13時(shí)“臨時(shí)”就替換為13，“臨時(shí)序號(hào)”變?yōu)?。一直對(duì)比到列表的末尾，這時(shí)“臨時(shí)”變量中記錄為17是列表1中最大的數(shù)值，“臨時(shí)序號(hào)”為5。這時(shí)將數(shù)據(jù)17放入列表2的第一個(gè)位置，并刪除列表中序號(hào)5的對(duì)應(yīng)數(shù)值17。依次循環(huán)直到列表1中沒(méi)有數(shù)據(jù)為止。

算法流程圖如圖3。

5.編程實(shí)現(xiàn)

（1）對(duì)小貓編程，建立列表1、列表2。建立變量臨時(shí)、序號(hào)、臨時(shí)序號(hào)。清空列表。

（2）重復(fù)5次，將隨機(jī)數(shù)加入表1。如圖4。

（3）重復(fù)執(zhí)行直到表1項(xiàng)目數(shù)為O。將序號(hào)、臨時(shí)序號(hào)設(shè)為1，將臨時(shí)設(shè)定為表1第1項(xiàng)。

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

（5）將臨時(shí)加入表2，刪除表1的臨時(shí)序號(hào)項(xiàng)。根據(jù)題目要求等待1秒。

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

6.解題思路B

本例中排序使用了臨時(shí)變量來(lái)存儲(chǔ)當(dāng)前最大的數(shù)。下面提供另外一種解題思路，只使用2個(gè)變量，序號(hào)和最大項(xiàng)序號(hào)。比較第1項(xiàng)和第2項(xiàng)，如果第2項(xiàng)大于第1項(xiàng)，則將第2項(xiàng)作為最大項(xiàng)序號(hào)。接下來(lái)比較第2項(xiàng)和第3項(xiàng)，如果第2項(xiàng)大于第3項(xiàng)，則將序號(hào)加1，第2項(xiàng)繼續(xù)與第4項(xiàng)比較。比較到列表最后將最大項(xiàng)序號(hào)對(duì)應(yīng)的值拷貝到表2中，并刪除。具體程序如圖6。