一、選擇排序(selection sort)

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，所以稱為：選擇排序。

二、選擇排序原理

設第一個元素為比較元素，依次和后面的元素比較，比較完所有元素并找到最小元素，記錄最小元素下標，和第0個下表元素進行交換。

在未排序區域中，重復上述操作，以此類推找出剩余最小元素將它換到前面，即完成排序。

三、選擇排序和冒泡排序對比

選擇排序是一種簡單直觀的排序算法。它與冒泡排序很相似，都是比較 n-1 輪，每輪都是比較 n–1–i 次，每輪找出一個最大值或最小值。

只不過，冒泡排序是將每輪找出的最值放到最右邊，而選擇排序是將每輪找出的最值放到最左邊。并且在算法上，冒泡排序是將相鄰的數進行逐個比較，以從小到大排序為例，只要前面的比后面的大，就互換這兩個數，直到最后將最大的數“浮”到最右邊，如此依次循環。而選擇排序是先保存第一個元素的下標，然后后面所有的數依次與第一個元素相比，如果遇到更小的，則記錄更小的那個數的下標，然后后面所有的數都依次與那個更小的數比較，直到最后將最小的數的下標找出來，然后再將這個數放到最左邊，即與下標為 0 的數互換。如果最小的數的下標就是 0 那么就不用互換。

所以，選擇排序算法是先判斷最小的數的下標是不是 0，如果不是則說明最小的數不是第一個元素，則將這個數與第一個元素互換位置，這樣一輪下來最小的那個數就被找到并放到了最左邊。

在第二輪同樣先保存新序列第二個元素的下標，后面所有的數依次與第二個元素相比較，如果遇到更小的則記錄更小的那個數的下標，然后后面所有的數都依次與那個更小的數比較，直到最后又找到一個最小的，此時這個最小的在整個序列中是“第二小”。然后再判斷這個數的下標是否等于 1，如果不等于 1 說明“第二小”的那個數不是第二個元素，則將這個數與第二個元素互換位置，這樣第二輪下來就找到了“第二小”的那個數，并將它放到了第二個位置。如此循環，直到整個序列實現從小到大排序。

如果是從大到小排序，那么就記錄大的那個數的下標，每一輪找出一個最大的數放到左邊。

從上面的分析可以看出，選擇排序和冒泡排序的另一個不同點是，冒泡排序只要遇到前面比后面大的就互換，而選擇排序是比較一輪才互換一次，而且如果本輪中最小的就是最左邊那個數則不用互換。所以從這個角度看，選擇排序比冒泡排序的效率要高。而且通過上面對選擇排序的分析發現，從邏輯上講，與冒泡排序相比，選擇排序更符合人的思維。

四、選擇排序流程圖

五、選擇排序的代碼實現(python)

def selection_sort(num_list):length = len(num_list)if length <= 1:return num_listfor j in range(length):# 假設第一個元素為最小元素min_num_index = j# 遍歷未排序區域元素，以此和未排序區域的第一個元素做對比for i in range(j+1, length):if num_list[i] < num_list[min_num_index]:min_num_index = i# 交換位置num_list[min_num_index], num_list[j] = num_list[j], num_list[min_num_index]return num_listif __name__ == '__main__':a = [1, 3, 2, 6, 4, 12, 33, 5, 25]print(selection_sort(a))

六、時間復雜度和空間復雜度

空間復雜度：只需要常數個輔助單元，所以空間復雜度為O(1)

時間復雜度：我們看到選擇排序同樣是雙層循環n*(n-1))，所以時間復雜度也為：O(n^2)

穩定性：因為存在任意位置的兩個元素交換，比如[5, 8, 5, 2]，第一個5會和2交換位置，所以改變了兩個5原來的相對順序，所以為不穩定排序。

是否為原地排序: 是原地排序

總結

以上是生活随笔為你收集整理的python 选择排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。