# 選擇排序
## 示意圖

## 運作步驟
1. 從第一個元素開始尋找最小(大)元素,存放在首位
2. 從剩余未排序的元素中繼續尋找最小(大)元素,放到已排序的序列末尾
3. 重復上面的步驟直到最后一個元素
## 助記碼
```
i∈[0,N) //循環N遍
j∈[i,N-1) //每遍循環要處理的無序部分
swap(i,min_index) //將最小(大)值和起始位置交換
```
## 算法分析
* 最壞時間復雜度 O(n^2)
* 最優時間復雜度 O(n^2)
* 平均時間復雜度 O(n^2)
## 實現
```Python
def selection_sort(list):
'''Python中的選擇排序算法實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
list_len = len(list)
for i in range(list_len):
min_index = i # 假設當前位置是最小元素位置,min_index = i
for j in range(i+1, list_len): # 遍歷后面的元素
if list[i] > list[j]: # 如果后面元素有比當前位置小的值,則將min_index更新為這個元素的位置
min_index = j
if not min_index == i: # 如果發現最小元素的鍵不是i,則將他們兩個的值交換
list[i], list[min_index] = list[min_index], list[i]
return list
```
## 測試
```
$ python selection_sort.py
選擇排序>>>
請輸入需要排序的數字,用英文半角逗號隔開,直接回車則使用默認數據:
需要排序的數字為:
8,-5,10,6,-23,15,45
排序結果:
-23,-5,6,8,10,15,45
```
# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)