摘要訊息 : 通過每次選擇集合中最小的元素進行排序的演算法.

0. 前言

對於任意集合, 如果每次都選出一個最小的元素, 然後把這個元素從集合中排除, 並且將每次選出的元素逐個排列, 最終也可以得到一個有序的集合.

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

更新紀錄 :

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

1. 搜尋集合中的最小元素

從一個集合中找到一個最小的元素非常簡單, 我們按照元素在集合中的排列, 順序地從前到後搜尋即可. 每次記錄遇到當前遇到的最小元素, 當搜尋完畢之後, 記錄的便是整個集合中的最小元素.

2. 選擇排序法

每一次找到集合中最小的元素之後, 與其把它從集合中移除掉, 放進新的集合, 不如通過交換把它放到原集合中對應的位置. 例如集合 \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \} 中, 最小的是 A, 這樣我們就交換 A 和 B 的位置, 使得 \mathscr {S} 中的第一個元素是 A. 因為 A 已經找到了正確的位置, 所以接下來搜尋最小元素就會把 A 排除在外, 在新的集合 \mathscr {S} \setminus \left \{ A \right \} 中搜尋最小的元素, 然後把最小的元素交換到 \mathscr {S} \setminus \left \{ A \right \} 的第一個元素. 不斷重複這個步驟, 直到集合元素被移除得只剩下一個, 這個就是原集合中最大的元素.

我們合稱 Algorithm 1 和 Algorithm 2 為選擇排序法 (selection sort).

例題 1. 對集合 \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \} 使用選擇排序法.

解 :

由於 \mathop {\mathbb {M}}(\left \{ B, C_{1}, P, A, C_{2}, K \right \}) = 4, 因此交換 \mathscr {S} 中第 1 個元素和第 4 個元素, 得到 \mathscr {S} = \left \{ A, C_{1}, P, B, C_{2}, K \right \}. \mathop {\mathbb {M}}(\left \{ C_{1}, P, B, C_{2}, K \right \}) = 3, 因此交換 \mathscr {S} 中第 2 個元素和第 3 + 1 = 4 個元素, 得到 \mathscr {S} = \left \{ A, B, P, C_{1}, C_{2}, K \right \}. \mathop {\mathbb {M}}(\left \{ P, C_{1}, C_{2}, K \right \}) = 2, 因此交換 \mathscr {S} 中第 3 個元素和第 2 + 2 = 4 個元素, 得到 \mathscr {S} = \left \{ A, B, C_{1}, P, C_{2}, K \right \}. \mathop {\mathbb {M}}(\left \{ P, C_{2}, K \right \}) = 2, 因此交換 \mathscr {S} 中第 4 個元素和第 2 + 3 = 5 個元素, 得到 \mathscr {S} = \left \{ A, B, C_{1}, C_{2}, P, K \right \}. \mathop {\mathbb {M}}(\left \{ P, K \right \}) = 2, 因此交換 \mathscr {S} 中第 5 個元素和第 2 + 4 = 6 個元素, 得到 \mathscr {S} = \left \{ A, B, C_{1}, C_{2}, K, P \right \}.

最終, \mathscr {S} 有序.

\blacksquare

3. 穩定性分析

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

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

證明 :

Algorithm 1 中使用了 < 運算子在元素之間進行比較. 設對集合 \mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \} 使用選擇排序法. 如果在第 i 個位置遇到最小的元素, 使得 m = i. 又在第 i + k 個位置遇到和 e_{i} 相等的元素, 此時 e_{i + m} < e_{i} 並不成立, 所以並不會使得 m 的值改變. 換句話說, e_{i} 在排序後集合 {\mathscr {S}}' 中的位置在 e_{i + k} 之前. 其中, i = 1, 2, ..., n, i + k \leq n.

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

\blacksquare

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

4. 即時終結的選擇排序法

現在, 我們更改一下 Algorithm 1 搜尋的過程. Algorithm 1 的搜尋是從集合頭部的開始, 現在我們將搜尋從集合尾部往前搜尋. 現在讓 m 的初始值為 n. 如果集合中的元素是有序的, 那麼每一次搜尋都會使得 m 的值發生更改, 因為有序的集合中, 更小的總是在前面. 一旦某一次搜尋過程中, m 的值沒有發生改變, 就說明該位置處, 至少有一個較大的元素排列在較小的元素前面. 這個時候, 我們可以斷定集合是無序的. 但是如果每一次搜尋, m 的值都發生改變, 那麼說明集合中剩下的元素不再需要排序, 這個時候我們讓選擇排序法即時終結, 可以提升演算法的效能.

5. 複雜度分析

選擇排序法是原地重排的排序法, 因此只需要一些輔助性的空間, 空間複雜度為 \Theta(1). 非即時終結的選擇排序法, 每一次搜尋都要尋訪 O(n) 個元素, 搜尋總共要進行 n - 1 次, 所以總體的時間複雜度是 (n - 1)O(n) = O(n^{2}). 最好的情況下, 搜尋的最少次數是 \Omega(n^{2}) 次; 最壞的情況下, 搜尋的次數是 O(n^{2}). 因此, 非即時終結的選擇排序法的時間複雜度是 \Theta(n^{2}). 現在我們分析即時終結的選擇排序法. 在最好的情況下時間複雜度是 \Theta(n), 因為我們只需要尋訪所有元素一次. 在最壞的情況下, 時間複雜度仍然是 O(n^{2}). 因此, 在平均情況下, 即時終結的選擇排序法的時間複雜度仍然是 \Theta(n^{2}).

6. 實作

#include <algorithm>

void selection_sort(int arr[], int size) {
    bool is_sorted {};
    for(auto i {0}; not is_sorted and i < size - 1; ++i) {
        auto min {i};
        is_sorted = true;
        for(auto j {i + 1}; j < size; ++j) {
            if(arr[j] < arr[min]) {
                min = j;
                continue;
            }
            if(is_sorted) {
                is_sorted = false;
            }
        }
        std::swap(arr[i], arr[min]);
    }
}

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