Scratch插入排序算法

1、Scratch插入排序算法作者：陳新龍來源：電腦報(bào)2021年第43期排序算法是編程考試中最常見的題目幾乎所有的筆試和面試都會(huì)考到，因?yàn)樗w現(xiàn)的就是程序員的算法基礎(chǔ)和邏輯思維能力，經(jīng)?？措娔X報(bào)的讀者們都知道，我們已經(jīng)講了多種排序算法比如冒泡排序、選擇排序、桶排序那么大家有沒有思考一個(gè)問題：為什么有那么多種的排序算法呢？首先是因?yàn)榕判虻乃悸肥蔷哂卸鄻有缘?，從不同的角度解決排序問題，就會(huì)產(chǎn)生不同的排序方法。另外，不同的排序算法各有優(yōu)勢(shì)和劣勢(shì)，當(dāng)數(shù)據(jù)規(guī)模不同時(shí)，可以選擇合適的排序算法。今天就和大家分享一個(gè)新的排序算法“插入排序”，插入排序分為前插序和后插序，它的基本思想是將數(shù)組的第一個(gè)數(shù)認(rèn)為是有序數(shù)組

2、，從后往前或者從前往后掃描該有序數(shù)組，把數(shù)組中剩余n-1個(gè)數(shù)，根據(jù)數(shù)值大小，有序插入到前面序列中，直至數(shù)組所有數(shù)有序排列為止。這樣的話，n個(gè)元素只需要進(jìn)行n-1趟排序，比多數(shù)排序算法的效率更高。待持元崔序列15327136156942朗一次擇序*(27)廠(Z75336156942第一次樣存:(36)27廠3653115|6942第二a：押序土(53)1(15273653|69142第四S1527365316942第五次n序：(42)152726r425369例如有一組數(shù)列為【53、27、36、15、69、42】。首先對(duì)于待排序數(shù)組中第一個(gè)元素53認(rèn)定為有序元素，所以排序從第二個(gè)元素27開始。

3、第一次排序時(shí)從有序數(shù)列中查找27插入的位置。27小于53應(yīng)插入在53之前，此時(shí)將27提取出來后，將53后移，將27放入原53點(diǎn)位置，便完成了第一次排序。第二次排序的時(shí)候從有序序列中找36的插入位置。36小于53,大于27,36的插入位置在27與53之間。此時(shí)將36提取出來后，將53后移，再將36放入原53所在位置，便完成了第二次的排序。剩余的數(shù)字15、69、42的排序過程相同，找到合適的位置通過移動(dòng)、插入的方法完成排序。最終的排序數(shù)列結(jié)果為【15、27、36、42、53、69】總計(jì)五次排序。了解了插入排序的運(yùn)行過程和思路后，我們可以嘗試著用Scratch將代碼拼搭出來。首先新建兩個(gè)列表用于存放

4、原始數(shù)列和排序后的數(shù)列，開始時(shí)將序列中所有的內(nèi)容全部清空。通過重復(fù)執(zhí)行的方法，將1-50之間的隨機(jī)數(shù)添加入原數(shù)列列表中（隨機(jī)數(shù)的范圍和重復(fù)執(zhí)行的次數(shù)可自定義）。其次新建“處理中”和“已排序”兩個(gè)關(guān)鍵變量。由于插入排序是從第二項(xiàng)開始，所以變量“處理中”表示需要插入排序的數(shù)列的序列位置。變量已排序”代表數(shù)列中已經(jīng)完成排序的數(shù)列組從第一項(xiàng)開始的，一直重復(fù)執(zhí)行直到處理中的項(xiàng)數(shù)大于數(shù)列項(xiàng)數(shù)的總和便可跳出循環(huán)。在循環(huán)中，將需要處理的數(shù)和已排序數(shù)列中的數(shù)字進(jìn)行比較大小，通過比較大小將處理中的數(shù)字插入到合適的位置。處理中的數(shù)排在已排序數(shù)列的下一個(gè)數(shù)字，同時(shí)處理中的數(shù)字跟隨著循環(huán)每次加一，直至循環(huán)數(shù)列末尾，排序結(jié)束。插入排序的優(yōu)點(diǎn)就