# 選擇排序 (Selection sort)

## 簡介

分成已排序和未排序的陣列，在未排序的陣列中搜尋出最小的數字，之後加入到已排序陣列的最後一位。

選擇排序法在使用**交換模式下**為**不穩定排序法**。
選擇排序法在使用**插入模式下**為**穩定排序法**。

## 舉例說明

假設使用選擇排序法將陣列中的值由小到大排序。

初始陣列為：[8,3,2,1,7,4,6,5]

那麼第一次排序時會由左至右在陣列中找到最小的值，並將之與第一個位置的值做交換，因此第一輪結束後的陣列為：[1,3,2,8,7,4,6,5]。

完整的排序結果如下圖所示：


## 算法

1. 選擇排序一共有 n-1 輪排序。
2. 每一輪排序又是一個循環。

### 循環的規則

1. 先假定當前這個數是最小數，然後和後面的每個數進行比較。
2. 如果發現有比當前數更小的數，就重新確定最小數，並得到索引值。
3. 當遍歷到陣列的最後時，就得到本輪的最小值和對應的索引。
4. 將目前的數與最小值交換。

## 時間複雜度
假設今天要對一陣列使用選擇排序法由小到大排序。

### 最佳：O(n^2^)

### 平均：O(n^2^)

### 最差：O(n^2^)

無論資料順序如何，都會執行兩個迴圈。

## 參考資料
- [選擇排序法詳解](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FHy4Cwch9u)