Selection Sort選擇排序

01為什麼需要它

看到這些關鍵字就想到它：交換或寫入次數要最少、比較便宜但搬動昂貴、每輪確定一個最終位置、只要前幾個、最少交換次數、不在乎穩定性的小資料。

02核心概念

選擇排序把陣列分成兩區：左邊是已排好的區域，右邊是未排序的區域。每一輪把未排序區從頭掃到尾，記住最小值在哪個索引，掃完再把它和未排序區的第一格交換，已排好的區域就長一格。n−1 輪之後前 n−1 格都定位了，剩下的最後一格一定是最大的，不用再處理。

正確性靠一個不變量：第 i 輪（從 0 算起）結束後，a[0..i] 是整個陣列最小的 i+1 個元素，而且由小到大排好。這一輪開始時，未排序區的每個元素都不小於已排好區的任何元素；挑出其中的最小值放到 a[i]，既不破壞順序，也保證它是剩下元素裡最小的，歸納下去就成立。和氣泡排序靠相鄰交換一步步把最大值推到尾端不同，選擇排序只記索引，確定之後一次交換就讓元素直接到達最終位置，所以交換最多 n−1 次。再進一步：把每一格連到「這格的元素排好後該去的位置」會形成若干個環，每次交換剛好從一個環拆出一個定位的元素，所以元素互不相同時，交換次數正好是 n − 環數，也就是只用交換排好序的最少次數。

複雜度：第 i 輪要比較 n−1−i 次，總共 (n−1) + (n−2) + … + 1 = n(n−1)/2。這個數字和輸入無關：不看完未排序區的每一格，就無法確定誰最小，沒有提前結束的機會。所以最好、平均、最壞都是 Θ(n²) 次比較，已經排好的陣列也要比 n(n−1)/2 次，只是交換 0 次。交換最多 n−1 次，寫入是 O(n)；只多用一個索引變數，額外空間 O(1)。

最常被忽略的是它不穩定：交換會把 a[i] 一口氣丟到後面，可能越過和它同值的元素。例如依分數排序 [(3, A), (3, B), (1, C)]，第一輪把 (3, A) 和 (1, C) 交換，得到 [(1, C), (3, B), (3, A)]，A、B 的順序反了。要穩定得改成取出最小值、中間元素右移一格再放回，但寫入次數會變成 O(n²)，最大的優點也沒了。另一個常見錯誤是在內層迴圈一看到更小的就交換，交換次數會退化成 O(n²)；內層只該更新索引。和鄰居比較：氣泡排序的交換次數等於逆序對數量，但穩定、能提前結束；插入排序在近乎有序時是 O(n)，小陣列實務上都選它；堆積排序則是選擇排序的升級版，把「掃一遍找最值」換成堆積的 O(log n)，整體變成 O(n log n)。

03演算法步驟

1. 1外層 i 從 0 跑到 n−2。此時 a[0..i−1] 已排好，a[i..n−1] 是未排序區。
2. 2設 m = i。內層 j 從 i+1 掃到 n−1，只要 a[j] < a[m] 就令 m = j。內層只更新索引，不交換。
3. 3內層結束後，若 m ≠ i 就交換 a[i] 與 a[m]。a[i] 從此是最終值，之後不再碰它。
4. 4最後一格不用跑：前 n−1 格放的都是較小的元素，剩下那格一定最大。要由大到小，把比較改成 >，每輪選最大值。
5. 5只要最小的 k 個，外層跑 k 輪就停，a[0..k−1] 就是答案，O(kn)。需要穩定時，把交換改成「取出 a[m]、把 a[i..m−1] 右移一格、放進 a[i]」。

04互動示範

和氣泡排序共用陣列 [5, 2, 9, 1, 7, 3, 8, 4]，由小到大。每一步看未排序區的一格：藍色是正在看的格子，黃色是目前的最小值候選，找到更小的，黃色就跳到那一格；掃完一輪，藍色的兩格就是這輪唯一的一次交換，綠色是左邊已排好的區域。注意第 2 輪和第 7 輪最小值本來就在定位，不用交換。最後比較 28 次、交換只有 5 次（這份資料有 3 個環，8 − 3 = 5，已經是最少）；同一份陣列用氣泡排序要交換 13 次。

05程式碼

基本版回傳交換次數，可以直接和氣泡排序對照；兩個變形分別是只跑前 k 輪取出最小的 k 個，以及用右移代替交換的穩定版。主程式用同分的紀錄跑一般版與穩定版，看交換如何打亂同分元素的順序。C++ 用樣板加比較函式，同一份程式碼能排整數，也能排紀錄。

# 選擇排序：每輪在未排序區找最小值，和未排序區的第一格交換
# 回傳交換次數，方便和其他排序對照
def selection_sort(a, key=lambda x: x):
    n = len(a)
    swaps = 0
    for i in range(n - 1):                  # 最後一格不用處理
        m = i                               # 只記最小值的索引，先不交換
        for j in range(i + 1, n):
            if key(a[j]) < key(a[m]):
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]         # 每輪最多交換一次，a[i] 從此固定
            swaps += 1
    return swaps


# 變形一：只跑前 k 輪，a[:k] 就是最小的 k 個（而且已排好），O(kn)
def smallest_k(a, k):
    n = len(a)
    for i in range(min(k, n)):
        m = min(range(i, n), key=a.__getitem__)   # 未排序區第一個最小值的索引
        a[i], a[m] = a[m], a[i]
    return a[:k]


# 變形二：穩定版。找到最小值後不交換，而是把 a[i..m-1] 右移一格再放進 a[i]
# 同值元素的相對順序不變，但寫入次數變成 O(n²)，失去選擇排序最大的優點
def stable_selection_sort(a, key=lambda x: x):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if key(a[j]) < key(a[m]):       # 嚴格小於：同值時留下最前面那個
                m = j
        x = a[m]
        while m > i:                        # 右移，不會越過任何同值元素
            a[m] = a[m - 1]
            m -= 1
        a[i] = x
    return a


if __name__ == "__main__":
    a = [5, 2, 9, 1, 7, 3, 8, 4]
    swaps = selection_sort(a)
    print(a, swaps)                         # [1, 2, 3, 4, 5, 7, 8, 9] 5
    print(smallest_k([5, 2, 9, 1, 7, 3, 8, 4], 3))   # [1, 2, 3]

    # 依分數排序，同分的 A 原本在 B 前面
    recs = [(3, "A"), (3, "B"), (1, "C")]
    selection_sort(recs, key=lambda r: r[0])
    print(recs)          # [(1, 'C'), (3, 'B'), (3, 'A')]  A、B 順序被打亂
    recs = [(3, "A"), (3, "B"), (1, "C")]
    stable_selection_sort(recs, key=lambda r: r[0])
    print(recs)          # [(1, 'C'), (3, 'A'), (3, 'B')]

06練習題

• LeetCode 414Third Maximum Number（跑三輪「選最大」，重複值只算一次）Easy
• LeetCode 2500Delete Greatest Value in Each Row（每輪各列選出最大值）Easy
• LeetCode 670Maximum Swap（由大到小的選擇排序只做一次交換）Medium
• LeetCode 969Pancake Sorting（每輪把最大值翻到尾端）Medium
• LeetCode 2471Minimum Number of Operations to Sort a Binary Tree by Level（最少交換 = n − 環數）Medium
• LeetCode 765Couples Holding Hands（另一種最少交換次數）Hard