選擇排序法 (Selection Sort)
介紹
工作原理：
- 每次從未排序的部分中找到最小（或最大）的元素。
- 將這個元素與未排序部分的第一個元素交換位置。
- 重複這個過程，直到所有元素都已排序。
假如給n個長度的列表，遍歷整個列表(遍歷n次)，每次都找出最小值，跟目前遍歷值i交換位置，最後剩下的就是最大的。
排序過程示例
- 初始數列：
- 第一輪：最小值為
，當前第一個元素 交換，變為 。 - 第二輪：未排序部分為
，最小值為 ，跟 交換，變為 。 - 第三輪：未排序部分為
，最小值為 ，跟 交換，變為 。
範例程式碼
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
lucashsu95