萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 選擇排序算法:三種實現變體與性能分析

算法核心思想

選擇排序每輪在未排序區間找到最小(大)元素,與區間首位交換。特點:

  • 時間複雜度 **O(n²)**(最好/最壞/平均同階),不受數據初始分布影響。
  • 空間複雜度 **O(1)** 原地排序。
  • 交換次數最少**(最多 n-1 次),適合寫入代價高的存儲介質(如 EEPROM、Flash)。
  • 不穩定**(相同元素相對順序可能改變)。

變體一:標準雙層循環(原地交換)


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

工程實踐建議

  1. 絕大多數場景直接用 list.sort() / sorted():Timsort 適應性強、C 實現、穩定、O(n log n)。
  2. 教學/面試/受限環境:掌握標準版 selection_sort_v1 邏輯,理解「最小交換次數」優勢。
  3. 寫入極其昂貴場景(如 EEPROM 燒錄):選擇排序或循環排序可減少寫入次數。
  4. 需穩定排序:選擇排序不穩定,改用插入排序、歸併排序或 Timsort。
  5. 大數據量:堆排序(heapq)或快速排序變體。

總結

選擇排序是「簡單但不高效」的經典教學算法。三種记體分別展示了:原地交換、函數式構建、交互式教學三種編程範式。實際開發中,**除非有極特殊約束(寫入代價高、嚴格 O(1) 空間、教學演示),永遠優先使用內建排序**。理解其「每輪選最小、交換一次」的核心邏輯,有助於理解堆排序等進階算法的演化脈絡。

copyright © 萬盛學電腦網 all rights reserved