Selection Sort Algorithm 選擇排序法
2022-10-23 23:04:09
# Selection Sort 選擇排序法
+ 是 **O(n^2)** 的排序演算法。
+ 每次選擇尚未排序的最小值，並跟陣列中尚未排序值的最左邊做位置的交換，換到左邊的值被視為已排序的陣列。
+ 所以選擇排序法最重要的兩個步驟，一是找到最小值，二是交換到左邊。
```
Selection Sort 的原理為：
從「未排序好的值」中找到最小值，並與「尚未排序的值」的最左邊做位置交換，
隨後將此值標示成「已排序好」，並開始下個循環，直到整個陣列都變成已排序好。
```
 
``` python
arr = [23, 45, 10, 5, -1, 9, -44, 0, -10, 57, 16]
def selectionSort(arr):
for i in range(len(arr)-1):
minIndex = i
for j in range(i, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# 內層 for 跑完，找出最小值並與最左邊(arr[i])換位
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
# [-44, -10, -1, 0, 5, 9, 10, 16, 23, 45, 57]
```
## 介紹
在選擇排序法中：
```for i in range(len(arr)-1)``` 先設立要排序的範圍，從第一格到倒數第二格，因為最後一格會自動排列
 
```minIndex = i``` 先假設 未排序值 最左就是最小值，並進去跑 **j** 迴圈，
從 index = i 後面找出是否有更小的值，有的話把該 index 宣告成 **minIndex**
 
`arr[i], arr[minIndex] = arr[minIndex], arr[i]`
找出來後就將 未排序值 的最左 **arr [ i ]** 與最小 **arr [ minIndex ]** 的值互換
## BigO
找確認最小值需要跑一個未排序資料長度，
「已排序好」的值也需要從陣列的 第一格 跑到 倒數第二格，用了兩層迴圈可以推判選擇排序法不是效率佳的演算法
Worst Case Performance: O(n^2)
Best Case Performance: O(n^2)
Average Performance: O(n^2)
 
## 參考資料：
[[演算法]-選擇排序法Selection Sort](https://ithelp.ithome.com.tw/articles/10276719)
[初學者學演算法｜排序法入門：選擇排序與插入排序法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)
Udemy - 資料結構與演算法 (JavaScript)
點擊複製文章連結
X