Scratch之插入 排序算法

在編程中我們經(jīng)常會(huì)用到排序，排序的目的是將一組“無(wú)序”的數(shù)列調(diào)整為“有序”的數(shù)列。

之前我們已經(jīng)通過(guò)解題接觸到了冒泡排序和選擇排序（參見2020年7期《藍(lán)橋杯青少年創(chuàng)意編程大賽 Scratch編程題解析（五）》）。

冒泡排序的思路是：比較相鄰的兩個(gè)數(shù)據(jù)，如果第二個(gè)數(shù)據(jù)比第一個(gè)數(shù)據(jù)小，交換位置，一直重復(fù)比較的操作，從開始的第一對(duì)到結(jié)尾的最后一對(duì)，比較結(jié)束之后，最后的元素是最大的數(shù)字，第一位是最小的元素。

選擇排序的思路是：第一次從全部的數(shù)列中找出最大或者是最小的數(shù)字放在序列的起始位置，然后再次從剩下未排序的數(shù)列中尋找最大或最小的數(shù)字，依次尋找，直到待排序的數(shù)據(jù)個(gè)數(shù)為零。

很多同學(xué)就會(huì)問(wèn)排序只有這兩種方法嗎？當(dāng)然不是，常用的排序算法就有十多種呢，希爾排序、歸并排序、基數(shù)排序……今天我們就來(lái)講一種比選擇排序和冒泡排序還要簡(jiǎn)單的排序算法——插入排序。

插入排序是所有排序中最簡(jiǎn)單的排序方法，它的思路是將一個(gè)記錄插入到已經(jīng)排列好的序列表中，從而產(chǎn)生一個(gè)新的、記錄數(shù)增加1的有序表，我們可以看看圖中的排序過(guò)程（如圖1）。

今天我們用Scratch來(lái)完成插入排序的代碼，首先我們給一組數(shù)列中插入5個(gè)數(shù)字，組成有序的數(shù)列。隨后隨機(jī)產(chǎn)生一個(gè)數(shù)字，比較數(shù)字大小，并將數(shù)字插入到有序的數(shù)列中組成新的有序數(shù)列。本例只為數(shù)列添加了一個(gè)新的數(shù)字，主要是為了體會(huì)算法思想，你需要根據(jù)實(shí)際情況靈活運(yùn)用。

我們將數(shù)字2，3，5，7，9有次序地插入到數(shù)列之中，這個(gè)數(shù)列目前是有序排列的。生成一個(gè)隨機(jī)數(shù)用來(lái)進(jìn)行插入。下面的算法就是如何把這個(gè)隨機(jī)數(shù)插入到這個(gè)有序的數(shù)列中的合適位置。

首先我們要判斷產(chǎn)生隨機(jī)數(shù)是否大于數(shù)列最后一位數(shù)字9，如果大于數(shù)字9的話，要加入到列表的最后一項(xiàng)，因?yàn)橄蛄斜砟┪惶砑訑?shù)是不能通過(guò)插入來(lái)實(shí)現(xiàn)的。

處理完新數(shù)字是最后一項(xiàng)的情況后，我們需要考慮插入的情況了。重復(fù)執(zhí)行，依次比較大小，如果比當(dāng)前數(shù)小，記錄當(dāng)前是第幾項(xiàng)，把新數(shù)字插入在這個(gè)位置前。

因此我們需要把列表中的數(shù)據(jù)全部循環(huán)一次，在循環(huán)的過(guò)程中，新數(shù)和數(shù)列中的每一項(xiàng)數(shù)字進(jìn)行比較，如果數(shù)列中的某一項(xiàng)數(shù)大于隨機(jī)數(shù)，那么將隨機(jī)數(shù)插入到這一項(xiàng)前面，并且停止所有的腳本，每次比對(duì)后，都需要對(duì)項(xiàng)數(shù)進(jìn)行加1，這樣才能依次比較（如圖2）。

總結(jié)：插入排序是最簡(jiǎn)單的排序算法，每次處理就是取無(wú)序的數(shù)列中第一個(gè)元素與有序數(shù)列的元素從后到前比較，找到插入位置，將該元素插入到有序數(shù)列的適當(dāng)位置上，由于這種算法沒(méi)有改變?cè)瓟?shù)列中相同大小元素的相對(duì)位置，因此稱之為穩(wěn)定排序算法。