選擇排序是一種簡(jiǎn)單直觀的排序算法犀勒，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候导帝，數(shù)據(jù)規(guī)模越小越好虚缎。唯一的好處可能就是不占用額外的內(nèi)存空間撵彻。
算法步驟
首先在未排序序列中找到最小（大）元素实牡，存放到排序序列的起始位置
再從剩余未排序元素中繼續(xù)尋找最心敖（大）元素，然后放到已排序序列的末尾创坞。
重復(fù)第二步碗短，直到所有元素均排序完畢。
# -*- coding:utf-8 -*-
def selection_sort(arr):
for i in range(len(arr) - 1):
# 記錄最小數(shù)的索引
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
# i 不是最小數(shù)時(shí)题涨，將 i 和最小數(shù)進(jìn)行交換
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
if __name__ == '__main__':
array = [2, 4, 1, 3, 5, 8, 7, 8, 4, 9]
print selection_sort(array)
選擇排序復(fù)雜度
1.時(shí)間復(fù)雜度：
- 平均時(shí)間復(fù)雜度：O(n^2)
- 最大時(shí)間復(fù)雜度：O(n^2)
- 最小時(shí)間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
比如序列5 8 5 2 9偎谁，第一遍選擇第1個(gè)元素5和2交換，那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了纲堵，所以選擇排序不是一個(gè)穩(wěn)定的排序算法巡雨。
選擇排序VS冒泡排序
- 冒泡排序通過依次交換相鄰兩個(gè)順序不合法的元素位置，從而將當(dāng)前最邢（大）元素放到合適的位置
- 選擇排序每遍歷一次都記住了當(dāng)前最蓄硗（大）元素的位置，最后僅需一次交換操作即可將其放到合適的位置茂附。
