前言

前面我們已經一起學習了冒泡排序（Python 實現經典算法之冒泡排序），這篇文章，大家與好奇心就一起再來看看選擇排序吧。

簡介

選擇排序是一種簡單直觀的排序算法，無論什么數據進去都是 O(n²) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。

原理

第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾（這里注意，是已排序好的末尾，不是數組末尾！）。以此類推，直到全部待排序的數據元素的個數為零。可以理解為一個 0 到 n-1 的迭代，每次向后查找選擇一個最小的元素。選擇排序是不穩定的排序方法。

步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾；
重復步驟 2，直到所有元素均排序完畢。

動圖演示

實例代碼

###
# author: 今日頭條：技術好奇心
###

# 選擇排序例子
def selection_sort(arr):
    # 按數組總長度來，依次遍歷
    for i in range(len(arr) - 1):
        # 存儲最小下標值(這里默認假設數組第一個為最小值)
        min_index = i
        # 以 j 為下標，i+1為起始位置，再次對數組進行遍歷
        # （因為之前的以及是最小值排序好了，所以起始為i+1）
        for j in range(i + 1, len(arr)):
            # 如果這個數小于之前記錄的最小數，則更新最小數的下標
            if arr[j] < arr[min_index]:
                min_index = j
        # 將 i 位置的數（前面已排序序列的末尾的數）和最小數進行交換
        arr[i], arr[min_index] = arr[min_index], arr[i]
        # 這里為了方便大家對比參考，所以每次比較完了就打印一次
        print(arr)


# 執行
if __name__ == '__main__':
    # 建立演示數組
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    # 執行排序方法
    selection_sort(arr)
    # 看看比較完之后數組的樣子
    print('-------------------- 技術好奇心 -------------------')
    print(arr)

運行結果：

[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]
-------------------- 技術好奇心 -------------------
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]