前言
前面我們已經(jīng)一起學(xué)習(xí)了冒泡排序（Python 實現(xiàn)經(jīng)典算法之冒泡排序），這篇文章，大家與好奇心就一起再來看看選擇排序吧。
簡介
選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進(jìn)去都是 O(n²) 的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。
原理
第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾（這里注意，是已排序好的末尾，不是數(shù)組末尾！）。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。可以理解為 一個 0 到 n-1 的迭代，每次向后查找選擇一個最小的元素。選擇排序是不穩(wěn)定的排序方法。
步驟
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
- 再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾；
- 重復(fù)步驟 2，直到所有元素均排序完畢。
動圖演示
實例代碼
###
# author: 今日頭條：技術(shù)好奇心
###
# 選擇排序例子
def selection_sort(arr):
# 按數(shù)組總長度來，依次遍歷
for i in range(len(arr) - 1):
# 存儲最小下標(biāo)值(這里默認(rèn)假設(shè)數(shù)組第一個為最小值)
min_index = i
# 以 j 為下標(biāo)，i+1為起始位置，再次對數(shù)組進(jìn)行遍歷
# （因為之前的以及是最小值排序好了，所以起始為i+1）
for j in range(i + 1, len(arr)):
# 如果這個數(shù)小于之前記錄的最小數(shù)，則更新最小數(shù)的下標(biāo)
if arr[j] < arr[min_index]:
min_index = j
# 將 i 位置的數(shù)（前面已排序序列的末尾的數(shù)）和最小數(shù)進(jìn)行交換
arr[i], arr[min_index] = arr[min_index], arr[i]
# 這里為了方便大家對比參考，所以每次比較完了就打印一次
print(arr)
# 執(zhí)行
if __name__ == '__main__':
# 建立演示數(shù)組
arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
# 執(zhí)行排序方法
selection_sort(arr)
# 看看比較完之后數(shù)組的樣子
print('-------------------- 技術(shù)好奇心 -------------------')
print(arr)
運行結(jié)果：
[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
-------------------- 技術(shù)好奇心 -------------------
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
從上面的結(jié)果來看，排序是成功的。
里面為了方便大家觀看對比，我將每次的執(zhí)行結(jié)果也打印出來了。
從過程中可以看出，排序是從數(shù)組第一個開始的，然后逐漸通過遍歷比較往后替換排序。
