選擇排序法教學：原理、程式碼與時間複雜度

用白話說明原理

掃描整個串列，找出最小的元素。把它與索引 0 的元素交換；現在索引 0 就是最終位置。接著從索引 1 開始掃描串列其餘部分，找出最小的並交換到索引 1。持續進行，直到只剩一個元素，那個元素必然是最大的。

與泡沫排序和插入排序不同，選擇排序不會因為輸入已排序而受益：它仍然得掃描每個剩餘元素，才能確定找到了最小值。

逐步範例

將 [64, 25, 12, 22, 11] 排序。直線之前的部分已排序並為最終位置。

五個元素共四步，共 4 + 3 + 2 + 1 = 10 次比較，以及三次實際的交換。

Python 實作

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

外層迴圈執行 n − 1 次，因為最後剩下的那個元素自然就在正確位置。內層迴圈只記錄索引；交換在每個外層步驟只發生一次。

時間與空間複雜度

寫入次數少是選擇排序唯一真正的優點。如果寫入記憶體比讀取昂貴得多（例如某些快閃記憶體，或搬移大型記錄時），減少寫入就可能很重要。循環排序（cycle sort）更進一步，每個元素至多只寫入一次。

穩定性：為什麼選擇排序不穩定

穩定排序會讓相等的元素保持原本的相對順序。選擇排序中的長距離交換，可能讓某個元素跳過另一個與它相等的元素。

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

2 與紅心 4 交換，使紅心 4 跑到黑桃 4 的後面。穩定版本也是有的：不用交換，而是移除最小值並插入到位置 i，其餘元素右移。這樣能保持順序，但每一步要花 O(n) 次寫入。

選擇排序與其他排序法的比較

堆積排序其實是用了更好資料結構的選擇排序：它同樣反覆選出剩餘元素中最大的，但用二元堆積在 O(log n) 內找到，而不是 O(n) 的掃描，使總時間降為 O(n log n)。

何時使用選擇排序

實際的 Python 程式請使用內建的 sorted() 或 list.sort()。選擇排序值得了解的場合包括：作為教學範例、在受限環境中處理大小固定的極小陣列，以及寫入次數必須降到最低時。它也是常見的考試與面試題，通常的問法是：追蹤每個步驟、計算比較與交換次數，並解釋為何它不穩定。