摘要訊息 : 每次向集合中插入元素的時候, 都讓元素找到合適的位置保持集合有序, 這樣就可以得到一個排序演算法.

0. 前言

對於一個空的集合, 如果每次插入元素之前, 我們通過比較找到該元素在集合中的位置, 使得插入元素之後集合仍然有序, 那麼最終我們得到的集合也是有序的. 這種思想也可以用在排序當中.

本篇文章中, 我們主要討論的是升序的插入排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 4 月 26 日進行第一次更新和修正.

1. 插入並保持有序

對於一個新的元素 $e_{n + 1}$, 如果要插入一個有序集合 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}$ 中, 我們可以先把 $e_{n + 1}$ 放到 $\mathscr {S}$ 的最後, 然後複製這個值得到一個副件 $e_{n + 1}'$. 現在, 我們從 $e_{n}$ 開始, 如果 $e_{n}$ 的值比 $e_{n + 1}'$ 大, 那麼就令 $e_{n + 1} = e_{n}$. 對於 $e_{n - 1}, e_{n - 2}, ...$ 都這樣處理, 直到找到一個 $e_{i}$ 滿足 $e_{i} < e_{n + 1}'$, 然後令 $e_{i + 1} = e_{n + 1}'$ 即可. 其中, $i = 1, 2, ..., n$. 這樣, 整個集合仍然有序.

例題 1. 設集合 $\mathscr {S} = \left \{ A, B, C_{1}, K, P \right \}$, 使用 Algorithm 1 插入新元素 $C_{2}$. 其中, $C_{1}$ 和 $C_{2}$ 數值上相等, 下標僅用於區分.

$解$ :

首先將 $C_{2}$ 放入 $\mathscr {S}$ 尾部得到 $\mathscr {S} = \left \{ A, B, C_{1}, K, P, C_{2} \right \}$. 比較 $P$ 和 $C_{2}$ 發現 $C_{2} < P$, 因此更新 $\mathscr {S}$ 得到 $\mathscr {S} = \left \{ A, B, C_{1}, K, P, P \right \}$. 比較 $K$ 和 $C_{2}$ 發現 $C_{2} < K$, 因此更新 $\mathscr {S}$ 得到 $\mathscr {S} = \left \{ A, B, C_{1}, K, K, P \right \}$. 比較 $C_{2}$ 和 $C_{2}$ 發現 $C_{2} < C_{1}$ 不成立, 因此更新 $\mathscr {S}$ 得到 $\mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \}$. 最終, $\mathscr {S}$ 有序.

$\blacksquare$

2. 插入排序法

當集合中不存在元素或者集合中有且唯有一個元素的時候, 集合就是有序的, 因此我們考慮集合中元素多於兩個的情況. 當集合中元素多於兩個的時候, 我們每次都取子集. 第一次取前兩個元素形成子集, 對這個子集使用 Algorithm 1, 這樣前兩個元素就保持有序了. 然後取前三個元素形成子集, 再次使用 Algorithm 1, 這樣前三個元素就保持有序了. 不斷重複這個過程, 直到取全部元素使用 Algorithm 1 之後, 整個集合就有序了.

我們合成 Algorithm 1 和 Algorithm 2 為插入排序法 (insertion sort).

3. 穩定性分析

們在《【演算法】名次排序法 (Ranking Sort)》中引入了排序演算法穩定性的定義 (見定義 1). 現在我們來分析一下由 Algorithm 1 驅動的插入排序法是否是穩定的排序.

斷言 1. 由 Algorithm 1 驅動的插入排序法是穩定的排序演算法.

$證明$ :

設集合 $\mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}$ 的子集 $\left \{ e_{1}, e_{2}, ..., e_{i} \right \}$ 已經有序. 其中, $i < n$. 若 $e_{i + 1}$ 和 $e_{j}$ 相等 ($j = 1, 2, ..., i$), 那麼 $e_{i + 1}$ 在 $\mathscr {S}$ 中的位置顯然排在 $e_{j}$ 之後. 由於 Algorithm 1 的比較和移動是從集合末尾開始往前的, 當 $e_{i + 1}$ 遇到 $e_{j}$ 時, Algorithm 1 會將 $e_{i + 1}$ 安排在 $e_{j + 1}$ 的位置. 這樣, $e_{i + 1}$ 在 $\mathscr {S}$ 中的位置仍然在 $e_{j}$ 之後.

綜上所述, 由 Algorithm 1 驅動的插入排序法是穩定的排序演算法.

$\blacksquare$

斷言 1 中並沒有直接斷言插入排序法就是穩定的演算法. 這是因為如果我們將 Algorithm 1 中的比較運算子換成 $\leq$ 或者 $\geq$, 那麼就會破壞排序的穩定性. 當然, 那些在 $\mathscr {S}$ 中相同的元素, 在 ${\mathscr {S}}'$ 中是倒序排列的.

4. 複雜度分析

插入排序法是原地重排的排序法, 因此只需要一些輔助性的空間, 空間複雜度為 $\Theta(1)$. 在最壞的情況下, 當我們每一次使用 Algorithm 1 的時候, 都需要移動 $O(n)$ 個元素. 在插入排序法中, Algorithm 1 會被使用 $n - 1$ 次, 所以選擇排序法的時間複雜度為 $(n - 1)O(n) = O(n^{2})$. 在最好的情況下, 我們不需要移動元素, 只需要進行比較, 因此時間複雜度為 $\Theta(1)$. 因為一共要比較 $n$ 次, 所以最好情況下的時間複雜度為 $\Theta(n)$. 平均情況下, 插入排序法的時間複雜度為 $\Theta(n^{2})$.

5. 實作

Code 1. 插入排序法
void insertion_sort(int arr[], int size) {
    for(auto i {1}; i < size; ++i) {
        auto j {i - 1};
        auto value {arr[i]};
        for(; j >= 0 and value < arr[j]; --j) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = value;
    }
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 insertion_sort 即可.