什麼是選擇排序？¶
選擇排序是一種簡單直觀的排序算法，它的核心思想是每次從待排序的元素中找出最小（或最大）的元素，然後將其放到已排序部分的末尾，直到所有元素都排好序。想象一下整理一疊打亂的撲克牌：你會從牌堆中一張一張挑出最小的牌，按順序放在桌子的左邊，直到所有牌都排好序。
選擇排序的步驟¶
- 初始化：假設數組的第一個元素是當前最小的元素（即位置0爲已排序部分的末尾）。
- 遍歷尋找最小值：從當前未排序部分的下一個元素開始，遍歷整個未排序區域，找到比當前最小值更小的元素，更新最小值的位置。
- 交換位置：將找到的最小值與當前未排序部分的第一個元素交換位置，此時該元素就被“固定”在已排序部分的末尾。
- 重複操作：重複上述步驟，直到未排序部分爲空（即所有元素都已排好序）。
Python代碼實現¶
下面是選擇排序的Python實現，代碼中包含詳細註釋，方便理解每一步：
def selection_sort(arr):
# 獲取數組長度
n = len(arr)
# 外層循環：控制需要排序的元素範圍（從0到n-2，因爲最後一個元素無需排序）
for i in range(n - 1):
# 假設當前位置i的元素是最小值
min_index = i
# 內層循環：從i+1到n-1尋找更小的元素
for j in range(i + 1, n):
# 如果找到更小的元素，更新最小值的位置
if arr[j] < arr[min_index]:
min_index = j
# 交換當前位置i的元素與找到的最小值元素
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 測試代碼
if __name__ == "__main__":
# 未排序的數組
unsorted = [64, 25, 12, 22, 11]
print("排序前：", unsorted)
# 調用選擇排序函數
sorted_arr = selection_sort(unsorted)
print("排序後：", sorted_arr)
代碼解釋¶
- 外層循環：變量
i從0到n-2（range(n-1)），表示已排序部分的末尾位置。每次循環結束後，arr[i]會被固定爲已排序部分的第i個元素（即最小值）。 - 內層循環：變量
j從i+1到n-1，遍歷未排序部分的所有元素，找到最小元素的位置min_index。 - 交換操作：找到最小值後，通過
arr[i], arr[min_index] = arr[min_index], arr[i]交換元素，確保最小值被“放到”已排序部分的末尾。
運行結果¶
運行上述測試代碼，輸出如下：
排序前： [64, 25, 12, 22, 11]
排序後： [11, 12, 22, 25, 64]
複雜度分析¶
- 時間複雜度：無論輸入數據如何，選擇排序都需要進行兩層循環（外層
n次，內層n次），因此時間複雜度爲O(n²)（n爲數組長度）。 - 空間複雜度：選擇排序是原地排序算法，不需要額外的數組空間，因此空間複雜度爲O(1)。
選擇排序的特點¶
- 簡單直觀：邏輯清晰，容易理解和實現，適合初學者學習排序算法的基本思想。
- 不穩定排序：如果數組中有相同元素，交換過程可能導致它們的相對順序改變（例如數組
[2, 2, 1]排序後可能變成[1, 2, 2]，但原數組中第一個2可能和第二個2的順序被交換）。 - 原地排序：不需要額外空間，僅通過交換元素完成排序。
選擇排序雖然時間複雜度較高，但在小規模數據排序中仍有實用價值，尤其適合理解排序算法的基本思想。通過上述步驟和代碼，你已經掌握瞭如何用Python實現選擇排序！