選擇排序法 (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)(原地排序)
- 穩定性:不穩定(交換可能會改變相同元素的相對順序)