Scratch插入排序算法

陳新龍

排序算法是編程考試中最常見的題目，幾乎所有的筆試和面試都會(huì)考到，因?yàn)樗w現(xiàn)的就是程序員的算法基礎(chǔ)和邏輯思維能力，經(jīng)?？础峨娔X報(bào)》的讀者們都知道，我們已經(jīng)講了多種排序算法比如冒泡排序、選擇排序、桶排序……

那么大家有沒有思考一個(gè)問題：為什么有那么多種的排序算法呢？首先是因?yàn)榕判虻乃悸肥蔷哂卸鄻有缘模瑥牟煌慕嵌冉鉀Q排序問題，就會(huì)產(chǎn)生不同的排序方法。另外，不同的排序算法各有優(yōu)勢(shì)和劣勢(shì)，當(dāng)數(shù)據(jù)規(guī)模不同時(shí)，可以選擇合適的排序算法。

今天就和大家分享一個(gè)新的排序算法“插入排序”，插入排序分為前插序和后插序，它的基本思想是將數(shù)組的第一個(gè)數(shù)認(rèn)為是有序數(shù)組，從后往前或者從前往后掃描該有序數(shù)組，把數(shù)組中剩余n-1個(gè)數(shù)，根據(jù)數(shù)值大小，有序插入到前面序列中，直至數(shù)組所有數(shù)有序排列為止。這樣的話，n個(gè)元素只需要進(jìn)行n-1趟排序，比多數(shù)排序算法的效率更高。

例如有一組數(shù)列為【53、27、36、15、69、42】。首先對(duì)于待排序數(shù)組中第一個(gè)元素53認(rèn)定為有序元素，所以排序從第二個(gè)元素27開始。第一次排序時(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è)列表用于存放原始數(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)就是穩(wěn)定，速度快，但是比較次數(shù)不一定，比較次數(shù)越少，插入點(diǎn)后的數(shù)據(jù)移動(dòng)越多，特別是當(dāng)數(shù)據(jù)總量龐大的時(shí)候，需要用鏈表解決這個(gè)問題。