選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法，將數(shù)列分為兩部分：排序部分和待選擇部分拆祈，每次從待選擇的數(shù)列選出最大或者最小的元素放置于起始位置。
算法思想
- 將第一個(gè)作為比較元素凳忙，一次和后邊的比較疫赎，完事兒找到最小的元素，和第一個(gè)元素比較檬姥；
- 重復(fù)操作曾我，直到找到第二小的元素和第二個(gè)元素互換，以此類推
代碼實(shí)現(xiàn)
def selection_sort(arr):
"""選擇排序"""
# 第一層for表示循環(huán)選擇的遍數(shù)
for i in range(len(arr) - 1):
# 將起始元素設(shè)為最小元素
min_index = i
# 第二層for表示最小元素和后面的元素逐個(gè)比較
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果當(dāng)前元素比最小元素小健民，則把當(dāng)前元素角標(biāo)記為最小元素角標(biāo)
min_index = j
# 查找一遍后將最小元素與起始元素互換
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
算法分析
與冒泡不同的是抒巢，每次只有一次數(shù)據(jù)交換，因而可以減少CPU消耗秉犹，實(shí)際使用還是少
- 比較性：需要比較來(lái)處理蛉谜，屬于比較排序
- 穩(wěn)定性：與冒泡不同稚晚，因?yàn)椴皇窍噜徳亟粨Q，所以肯定會(huì)發(fā)生相同元素之間的換位型诚，所以屬于不穩(wěn)定排序
- 時(shí)間復(fù)雜度：與冒泡一樣客燕，同樣是雙層循環(huán)
n(n-1)，所以是O(n^2) - 空間復(fù)雜度：只需常數(shù)輔助單元狰贯，所以是
O(1) - 內(nèi)層循環(huán)做對(duì)比的時(shí)候也搓，遇到小的元素只是先更改
min_index的指向，等到一輪內(nèi)層循環(huán)結(jié)束才會(huì)進(jìn)行數(shù)據(jù)交換涵紊，因?yàn)閮?nèi)層只有一次數(shù)據(jù)交換傍妒。
