Scratch之插入 排序算法

在編程中我們經常會用到排序，排序的目的是將一組“無序”的數列調整為“有序”的數列。

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

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

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

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

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

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

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

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

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

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

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