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

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. 實作

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 即可.