Skip to content
本站總訪問量
本站訪客數 人次

選擇排序法 (Selection Sort)

介紹

工作原理:

  1. 每次從未排序的部分中找到最小(或最大)的元素。
  2. 將這個元素與未排序部分的第一個元素交換位置。
  3. 重複這個過程,直到所有元素都已排序。

假如給n個長度的列表,遍歷整個列表(遍歷n次),每次都找出最小值,跟目前遍歷值i交換位置,最後剩下的就是最大的。

排序過程示例

  • 初始數列7,5,9,1,3
  • 第一輪:最小值為 1,當前第一個元素 7 交換,變為 1,5,9,7,3
  • 第二輪:未排序部分為 5,9,7,3,最小值為 3,跟 5 交換,變為 1,3,9,7,5
  • 第三輪:未排序部分為 9,7,5,最小值為 5,跟 9 交換,變為 1,3,5,7,9

範例程式碼

python
def selection_sort(arr):
    n = int(len(arr))
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 測試
arr = [64, 25, 12, 22, 11]
print("未排序數列:", arr)
sorted_arr = selection_sort(arr)
print("選擇排序後的數列:", sorted_arr)

性能特徵

  • 最佳情況時間複雜度:O(n²)
  • 最壞情況時間複雜度:O(n²)
  • 平均時間複雜度:O(n²)
  • 空間複雜度:O(1)(原地排序)
  • 穩定性:不穩定(交換可能會改變相同元素的相對順序)

學習資源

Contributors

The avatar of contributor named as lucashsu95 lucashsu95

Changelog