排序，是演算法中的基礎，也很常會在生活中用到，像是整理書籍、學校的學號排列等等。

在排序中，一開始也會需要先決定要 升序 (Ascending) 還 降序 (Descending)，也就是 由小到大 或是 由大到小。

那排序中會有一些名詞我們可以先來了解 。

首先是「穩定排序」及「不穩定排序」

• 當兩個相同的東西排序過後，相對位置不變，叫做穩定排序
• 當兩個相同的東西排序過後，相對位置改變，叫做不穩定排序

想像我們現在拿了一手撲克牌：{♥7, ♥3, ♦9, ♣7, ♣10, ♠A}

我們現在要照數字來排列，但現在有兩個 7，一個 ♥ 在前面，一個 ♣ 在後面，在經過排列之後

穩定排序：{♥3, ♥7, ♣7, ♦9, ♣10, ♠A} (相對位置不變)

不穩定排序：{♥3, ♣7, ♥7, ♦9, ♣10, ♠A} (相對位置改變)

再來是「內部排序」及「外部排序」

想像手裡拿著一副撲克牌

內部排序：撲克牌全部拿在手上來回排列 (在原本空間內排列)

外部排序：撲克牌一張一張放到桌子上排列 (在另外的空間排列)

插入排序法 (Insertion Sort)

插入排序法是一個非常簡單直觀的排序演算法，我覺得很適合先學習。

跟前面一樣想像我們現在拿了一手撲克牌：{♥7, ♥3, ♦9, ♣7, ♣10, ♠A, ♥8}，準備要開始打牌了，首先要先由小到大整理手中的牌。

1. 拿起 ♥3 往前比後插到 ♥7 左邊，結果： {♥3, ♥7 | ♦9, ♣7, ♣10, ♠A, ♥8}
2. 再來 ♥7、♦9 發現都不需要動，結果： {♥3, ♥7, ♦9 | ♣7, ♣10, ♠A, ♥8}
3. 拿起 ♣7 往前比後插到 ♥7 左邊或右邊，結果： {♥3, ♥7, ♣7, ♦9 | ♣10, ♠A, ♥8}
4. 再來 ♣10 發現不需要動，結果： {♥3, ♥7, ♣7, ♦9, ♣10 | ♠A, ♥8}
5. 拿起 ♠A 往前比後插到 ♥3 左邊，結果： {♠A, ♥3, ♥7, ♣7, ♦9, ♣10 | ♥8}
6. 拿起 ♥8 往前比後插到 ♦9 左邊，結果： {♠A, ♥3, ♥7, ♣7, ♥8, ♦9, ♣10}

• 另外步驟 4，如果 ♣7 插到 ♥7 左邊就是 不穩定排序，插到右邊則是穩定排序，但一般的插入排序法都是穩定排序。

插入排序法就像平常整理撲克牌的時候，在手上分成排完的跟沒排完的，再從沒排完的中，拿起一張放到排完的裡面合適的位置。

我們舉 4 - 5 步驟為例子：

分為排序好的跟還沒排的

從還沒排的挑最前面那個，一個一個往前 交換，直到找到一張比自己小的，或是前面沒有牌了，就停在那裡。

像這裡的 ♠A 就是發現前面沒東西了就停在那裡，再排進去到排序好的那邊。

再來同理，挑還沒排的最前面那個，持續同樣的操作，直到排完。

像這裡的 ♥8 就是發現前面的比自己小，就停在那裡了。

參考簡易程式碼 (Python)

def insertion_sort(unsorted):
    for i in range(1, len(unsorted)): # 因為第 0 位剛開始不需要排列，所以從 1 開始
        key = unsorted[i]             # 拿未排序最前面的做 key
        j = i - 1                         # i - 1 會等於已排序的長度

        # 往左邊已排序的區域尋找適合插入的位置
        while j >= 0 and unsorted[j] > key:   # 代表已排序的比完了或是前一個比自己小就結束
            unsorted[j+1] = unsorted[j]  # key 往前換位置
            j -= 1
        unsorted[j+1] = key         # 插入 key
        
    return unsorted


nums = [3, 5, 7, 1, 2, 15, 4]
print("未排序資料：", nums)
print("排序後：", insertion_sort(nums))

謝謝！

參考資料
增井敏克，《圖解演算法原理》，碁峰資訊，2023 年
ChatGPT