排序的方法有很多種，今天介紹一下“冒泡法”排序。

冒泡法排序的原理：對相鄰的元素進(jìn)行兩兩比較，順序相反則進(jìn)行交換。這樣，每一次會將最小或最大的元素“浮”到頂端，最終達(dá)到完全有序。

具體可參見上面的圖示。下面用Scratch進(jìn)行實(shí)現(xiàn)。

程序?qū)崿F(xiàn)：下圖是排序算法部分。

本例只對5個(gè)小球進(jìn)行排序，所以循環(huán)上限是5次。

其中，列表“序號”中存放了需要排序的內(nèi)容。變量i是外循環(huán)計(jì)數(shù)，循環(huán)次數(shù)為5；變量j是內(nèi)循環(huán)計(jì)數(shù)，循環(huán)次數(shù)是5-i。

難點(diǎn)一：為什么內(nèi)循環(huán)的次數(shù)是5-i？

l? 由于是兩兩進(jìn)行比較，所以第一次比較時(shí)，只需要比較4次就可以了。而第一次運(yùn)行時(shí)，外循環(huán)變量i=1，所以這時(shí)5-1=4；

l? 第二次執(zhí)行內(nèi)循環(huán)時(shí)，由于最大的已經(jīng)冒泡到頂部，只剩下4個(gè)元素。這4個(gè)元素，也只要比較3次就可以。而這時(shí)外循環(huán)變量i=2，剛好5-2=3。后面的依次類推。

難點(diǎn)二：如何引用數(shù)組結(jié)構(gòu)中的元素？

在Scratch中沒有提供“數(shù)組”這種數(shù)據(jù)結(jié)構(gòu)，但是提供了“列表”。數(shù)組可以通過列表來實(shí)現(xiàn)。

例如，有數(shù)組A，它有5個(gè)元素。則每個(gè)元素分別為A(1)、A(2)、A(3)、A(4)和A(5)。有的編程語言數(shù)組的下標(biāo)從0開始，有的從1開始。有的編程語言支持對數(shù)組的整體操作，有的只能一個(gè)元素一個(gè)元素的訪問。

Scratch中只有列表，所以只能通過下標(biāo)，一個(gè)個(gè)的訪問。

?“交換”部分程序如下：

難點(diǎn)三：如何交換兩個(gè)數(shù)據(jù)？

在程序中，兩個(gè)變量必須通過第三個(gè)變量才能實(shí)現(xiàn)交換。因?yàn)樵诖蟛糠志幊陶Z言中，等號的含義是“賦值”。

所以有的編程語言為了進(jìn)行區(qū)分，將賦值號寫成“：=”的形式。例如：

其含義是將100這個(gè)值賦予變量a。

因此直接寫成下列形式，是不能交換變量a和b的值的：

執(zhí)行第一條語句時(shí)，將變量b的值賦予了變量a，這時(shí)變量a的值已經(jīng)等于變量b了。所以執(zhí)行第二條語句時(shí)，只是再一次把值賦予變量b。變量a的值丟失了。

通常采用中間變量來實(shí)現(xiàn)交換。例如：

這里temp就是中間變量。注意其中的次序不能搞錯(cuò)。

完整的視頻如下所示：

后記：在利用冒泡法排序時(shí)，如果某次循環(huán)中沒有發(fā)生交換，說明所有數(shù)據(jù)都已經(jīng)排好了順序。這時(shí)可以中止循環(huán)，直接宣布排序結(jié)束。通常的做法是設(shè)置一個(gè)標(biāo)志變量flag。開始時(shí)設(shè)置flag=0；當(dāng)可以提前中止時(shí)，設(shè)置flag=1。Scratch語言中沒有break等中斷循環(huán)的命令，一般是設(shè)置一個(gè)快速變量。這樣條件判斷部分就變得稍微復(fù)雜一些。

下面是跟算法無關(guān)的一些內(nèi)容，只是為了讓程序更有趣：

1、按住“R”鍵可以重置需要排序的序列。新的序列是隨機(jī)生成的。再次按“空格”鍵可以開始排序；

2、設(shè)計(jì)了一條小魚可以提供各種信息，例如“排序結(jié)束”等。為了讓我們的泡泡魚缸更生動(dòng)形象，小魚會在魚缸中“漫步”。

3、為了更直觀的展示排序過程，對5個(gè)小球進(jìn)行了編號。編號可以去掉，排序的泡泡也可以換成你希望的物品哦。

聲明：本文章由網(wǎng)友投稿作為教育分享用途，如有侵權(quán)原作者可通過郵件及時(shí)和我們聯(lián)系刪除