選擇排序 Selection sort

Selection sort 是最易實作的入門排序法之一,會將資料分為 sorted pile 與 unsorted pile,每次從 unsorted pile 尋找最大/最小值,加入 sorted pile 中。

Selection sort 的特性如下:

  • 最簡單的排序法之一。
  • 對小資料序列排序效率較高。
  • 不穩定排序:排序後,相同鍵值的元素相對位置可能改變。
  • 原地排序:不需額外花費儲存空間來排序。

步驟

  1. 將資料分為 sorted pile 與 unsorted pile。
  2. 從 unsorted pile 尋找最小值。
  3. 置換該最小值元素與 unsorted pile 第一個元素。
  4. 重複步驟 2 - 3,直到排序完成。

注意,這個 naïve 的 selection sort 實作為不穩定排序

Joestape89 - CC BY-SA 3.0

說明

為什麼 naïve 的 selection sort 會是不穩定排序?

假定有一個序列要遞增排序,其中有重複的 2 元素,我們將其標上 2a2b 以利辨識。

[2a, 3, 4, 2b, 1]

開始迭代找出最小值並指環。

 *             *
[1, 3, 4, 2b, 2a] # 1. 置換 2a, 1

     *     *
[1, 2b, 4, 3, 2a] # 2. 置換 3, 2b

        *       *
[1, 2b, 2a, 3, 4] # 3. 置換 4, 2a

有沒有發現,2a2b 的相對順序顛倒了呢?

首先,回想一下穩定排序的定義:相同鍵值的元素,排序後相對位置不改變。

問題出在 naïve selection sort 是以置換的方式排序每次迭代的最小值。若我們將置換(swap)改為插入(insert),那麼 selection sort 就會是穩定排序,但相對地,需要位移剩餘未排序的元素,除非使用 linked list 或其他提供 $O(1) $ insertion 的資料結構,不然就會多出額外 $O(n^2) $ 的寫入成本。

效能

Complexity
Worst$O(n^2) $
Best$O(n^2) $
Average$O(n^2) $
Worst space$O(1) $ auxiliary

對於接近排序完成的序列,selector sort 並無法有自適應的方式加快排序迭代。第一個元素要做 $n - 1 $ 次比較,第二個 $n - 2 $ 次,總比較次數如下:

$$ (n -1) + (n-2) + \cdots + 1 = \sum_{i=1}^{n-1} i = \frac{n(n - 1)}{2}$$

因此無論序列是否排序完成,selection sort 仍需執行 $n^2 $ 次比較,時間複雜度為 $O(n^2) $。

實作

簡單實作如下:


# #![allow(unused_variables)]
#fn main() {
pub fn selection_sort(arr: &mut [i32]) {
    let len = arr.len();
    for i in 0..len {                     // 1
        let mut temp = i;
        for j in (i + 1)..len {           // 2
            if arr[temp] > arr[j] {
                temp = j;
            }
        }
        arr.swap(i, temp);                // 3
    }
}
#}
  1. 外層迴圈負責儲存當前要排序的 index i 的位置。
  2. 內層迴圈負責在 unsorted pile 範圍 [i, len) 找最小值。
  3. 外層迴圈在找到最小值之後,置換兩元素。

眼尖的人會發現,內外兩層迴圈的 upper bound 都是 len,這樣是否內側迴圈會 out of bound?Rust 的 range operator(core::ops::Range)實作 Iterator trait 時,有檢查 range.start < range.end,因此這個寫法並不會有出界問題,但會多跑一次無意義的迭代。

變形

Heapsort

Heapsort 是一個高效的排序法,使用 selection sort 融合 heap 這種半排序的資料結構,讓時間複雜度進化至 $O(n \log n) $。更多詳情可以參考這篇介紹

參考資料