理論程式設計——插入演算法（insertion sort）

>>github ：

redAntCpp/TheoryCoding

由上篇知道，往陣列中插入一個新的元素，需要將後面的元素都往後挪動一位，目的是為了騰出空位給新的元素插入。而刪除則是採取的直接覆蓋的方式。利用此原理，我們更好的理解接下來要介紹的排序演算法。

想象一個場景，鬥地主時，發牌後，我們手裡的牌此時是亂的。我們需要將它稍作整理。我們的做法是，先找一張牌，然後找到適合它的位置，擠出空位，然後插入。

插入演算法用的正是這一原理。

圖片引自CLRS

我們先假定有一串這樣的數字：

56 25 37 58 95 19 73 30

現要將上面的一串數字轉換為已排序狀態：

19 25 30 37 56 58 73 95

基本思路是這樣的：

我們假定25之前的數字序列都是排好序的。

那麼我們只需要將25向前插入，一旦遇到比25大的數，那麼就把25插入這個數的前面，直到找到比25小的數，然後停止。此時25已經排序完畢

接著對25後面的37進行同樣的操作。

選擇25是因為25前面只有一個元素56，56前面已經沒有元素了，說明它已經排好序了。一個元素不需要排序。

下面用圖形的方式來描述第一輪的過程

一開始我們的數列是這樣的：

2。 假設我們從第一輪（i 代表輪次）開始，用key記錄此時的簡要插入的值。

3。 此時與前方的元素做判斷，如果較大，則插入，較小則不動。此案例中應該交換

4。 然後用key的值來插入騰出的空位

值得注意的是，此時的“騰出位置”與之前的editor的做法有所不同。editor的操作是在現有的元素組基礎上插入一個新的元素。此時元素的數量+1，因此要全部往後挪動一位才能空出空位。否則將丟失最後一位的資料。

但此時的做法是在現有的元素基礎調整元素的順序。所以我們只需要覆蓋需要調整的數字，並記錄要覆蓋的值即可。

程式碼詳見 github。

貼上程式碼執行示例：