選擇排序每輪在未排序區間找到最小(大)元素,與區間首位交換。特點:
def selection_sort_v1(arr: list) -> None:
"""原地選擇排序,標準教科書寫法"""
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 測試
a = [64, 25, 12, 22, 11]
selection_sort_v1(a)
print(a) # [11, 12, 22, 25, 64]
優點:邏輯清晰、無額外空間、交換次數最少。
缺點:大量比較操作,Python 層面循環慢。
def selection_sort_v2(arr: list) -> list:
"""返回新排序列表,不修改原數據"""
working = arr[:] # 複製
result = []
while working:
min_val = min(working) # O(n) 找最小
result.append(min_val)
working.remove(min_val) # O(n) 移除首個匹配
return result
# 注意:此版本實際為 O(n²) 但常數因子極大(min + remove 各一次掃描)
# 僅適合教學演示或極小數據量
def selection_sort_interactive():
"""從控制台讀取數據並排序,展示每輪狀態"""
try:
n = int(input("輸入元素個數: "))
arr = []
for i in range(n):
val = int(input(f"第 {i+1} 個元素: "))
arr.append(val)
except ValueError:
print("輸入無效")
return
print("原始數組:", arr)
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(f"第 {i+1} 輪交換: {arr}")
print("最終結果:", arr)
# 運行: selection_sort_interactive()
每輪同時找最小值放左端、最大值放右端,循環輪數減半。
def selection_sort_bidirectional(arr: list) -> None:
left, right = 0, len(arr) - 1
while left < right:
min_idx, max_idx = left, right
for i in range(left, right + 1):
if arr[i] < arr[min_idx]: min_idx = i
if arr[i] > arr[max_idx]: max_idx = i
# 交換最小值到左端
arr[left], arr[min_idx] = arr[min_idx], arr[left]
# 若最大值原本在 left,交換後它已移至 min_idx
if max_idx == left:
max_idx = min_idx
# 交換最大值到右端
arr[right], arr[max_idx] = arr[max_idx], arr[right]
left += 1
right -= 1
用**堆**維護未排序區的最小值,將找最小從 O(n) 降為 O(log n),整體複雜度達 **O(n log n)**。Python 內建 heapq 即是此思想。
import heapq
def heap_sort(arr: list) -> list:
"""利用堆實現的選擇排序優化版"""
heapq.heapify(arr) # 原地建最小堆 O(n)
return [heapq.heappop(arr) for _ in range(len(arr))] # n 次 O(log n) 彈出
import random, time
def benchmark():
sizes = [1000, 2000, 5000]
for n in sizes:
data = [random.randint(0, 10000) for _ in range(n)]
print(f"\n=== n = {n} ===")
for name, fn in [
('selection_sort_v1', selection_sort_v1),
('selection_sort_bidirectional', selection_sort_bidirectional),
('heap_sort (heapq)', lambda a: heapq.heapify(a) or [heapq.heappop(a) for _ in range(len(a))]),
('built-in sorted', sorted),
]:
t0 = time.time()
fn(data.copy())
print(f"{name:30} : {time.time() - t0:.4f}s")
# 輸出參考:
# n = 1000
# selection_sort_v1 : 0.0152s
# selection_sort_bidirectional : 0.0098s
# heap_sort (heapq) : 0.0012s
# built-in sorted : 0.0003s
list.sort() / sorted():Timsort 適應性強、C 實現、穩定、O(n log n)。selection_sort_v1 邏輯,理解「最小交換次數」優勢。heapq)或快速排序變體。選擇排序是「簡單但不高效」的經典教學算法。三種记體分別展示了:原地交換、函數式構建、交互式教學三種編程範式。實際開發中,**除非有極特殊約束(寫入代價高、嚴格 O(1) 空間、教學演示),永遠優先使用內建排序**。理解其「每輪選最小、交換一次」的核心邏輯,有助於理解堆排序等進階算法的演化脈絡。