Scratch之插入 排序算法

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

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

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

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

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

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

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

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

首先我們要判斷產(chǎn)生隨機(jī)數(shù)是否大于數(shù)列最后一位數(shù)字9，如果大于數(shù)字9的話，要加入到列表的最后一項，因為向列表末位添加數(shù)是不能通過插入來實現(xiàn)的。

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

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

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