選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間。
算法步驟
首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/p>
再從剩余未排序元素中繼續(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ù)時，將 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.時間復(fù)雜度：
- 平均時間復(fù)雜度：O(n^2)
- 最大時間復(fù)雜度：O(n^2)
- 最小時間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
比如序列5 8 5 2 9，第一遍選擇第1個元素5和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩(wěn)定的排序算法。
選擇排序VS冒泡排序
- 冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當(dāng)前最小（大）元素放到合適的位置
- 選擇排序每遍歷一次都記住了當(dāng)前最?。ù螅┰氐奈恢?，最后僅需一次交換操作即可將其放到合適的位置。
