前言

Selection Sort 和 Bubble Sort 一樣，都是基本的排序法，時間複雜度都是 $O(n^2)$，屬於 unstable sorting

概念

Selection Sort 就是每次選最小的值然後不斷和 array 的第一個值做交換，Bubble Sort 則是兩兩一直交換

因為是不斷選擇最小的值放到最前面，所以每次迴圈都會少一個搜尋，因為前面已經排好了
流程大致如下：

  1. 找最小的值
  2. 把最小的值和目前 array 的第一個值做交換
  3. 從剩下的 array 重複 1 和 2 的過程

pseudo code

1
2
3
4
5
6
7
SelectionSort(A[1..n])
  for i from i to n:
    minIndex ← i
    for j from i+1 to n:
      if A[j] < A[minIndex]:
        minIndex ← j        // 只需紀錄index
      swap(A[i], A[minIndex])

複雜度比較

時間複雜度

Sequence Complexity
Random $O(N^2)$
Nearly Sorted $O(N^2)$
Reversed $O(N^2)$
Few Unique $O(N^2)$

Selection sort 的時間複雜度在所有情況下都是 $O(N^2)$，獨立於資料的組成

空間複雜度

沒有用到額外的 array，$O(1)$ space

可以到 Toptal 的這個網頁觀看不同 case 的視覺化排序過程