選擇排序：最簡單排序之一，最少交換實現方法

排序是計算機科學中的基礎操作，它能將一組數據按照特定順序（如升序）排列。在衆多排序算法中，選擇排序（Selection Sort）因其簡單性和最少交換的特點，成爲初學者入門的首選算法之一。接下來，我們將一步步揭開選擇排序的神祕面紗，理解它爲何簡單，以及爲何交換次數最少。

一、選擇排序的核心思路¶

選擇排序的核心思想非常直觀：每次從待排序的元素中找到最小（或最大）的那個元素，將它放到已排序部分的末尾。具體來說，我們可以將數組分爲兩個部分：已排序部分（初始爲空）和未排序部分（初始爲整個數組）。通過不斷在未排序部分中“挑選”最小元素，並與未排序部分的第一個元素交換位置，逐步將整個數組排序。

二、詳細步驟演示（以升序爲例）¶

假設我們要對數組 [64, 25, 12, 22, 11] 進行升序排序，具體步驟如下：

1. 初始狀態¶

已排序部分：[]（空）
未排序部分：[64, 25, 12, 22, 11]

2. 第一輪：找到未排序部分的最小元素¶

未排序部分的元素爲 [64, 25, 12, 22, 11]，最小元素是 11（位於索引 4）。
將最小元素 11 與未排序部分的第一個元素（即索引 0 的 64）交換，數組變爲：[11, 25, 12, 22, 64]。
此時，已排序部分：[11]，未排序部分：[25, 12, 22, 64]。

3. 第二輪：處理剩餘未排序部分¶

未排序部分的元素爲 [25, 12, 22, 64]，最小元素是 12（位於索引 2）。
將 12 與未排序部分的第一個元素（即索引 1 的 25）交換，數組變爲：[11, 12, 25, 22, 64]。
此時，已排序部分：[11, 12]，未排序部分：[25, 22, 64]。

4. 第三輪：繼續處理¶

未排序部分的元素爲 [25, 22, 64]，最小元素是 22（位於索引 3）。
將 22 與未排序部分的第一個元素（即索引 2 的 25）交換，數組變爲：[11, 12, 22, 25, 64]。
此時，已排序部分：[11, 12, 22]，未排序部分：[25, 64]。

5. 第四輪：最後處理¶

未排序部分的元素爲 [25, 64]，最小元素是 25（位於索引 3），無需交換。
已排序部分：[11, 12, 22, 25]，未排序部分：[64]。

6. 完成排序¶

未排序部分僅剩 64，已排序部分變爲 [11, 12, 22, 25, 64]，排序結束。

三、爲什麼選擇排序交換次數最少？¶

選擇排序的交換次數是最少的，原因在於：
每次僅需將找到的最小元素與未排序部分的第一個元素交換一次，不會像冒泡排序那樣頻繁交換相鄰元素。例如，對於長度爲 n 的數組，選擇排序最多隻需 n-1 次交換（每次處理一個元素，交換一次），而冒泡排序在最壞情況下可能需要 n(n-1)/2 次交換。

四、代碼實現（Python 示例）¶

以下是選擇排序的 Python 實現，核心邏輯與上述步驟一致：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假設當前位置i的元素是未排序部分的最小元素
        min_index = i
        # 在未排序部分（i到n-1）中尋找最小元素的索引
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 交換當前位置i的元素與最小元素
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 測試
arr = [64, 25, 12, 22, 11]
print(selection_sort(arr))  # 輸出：[11, 12, 22, 25, 64]

五、時間複雜度與空間複雜度¶

時間複雜度：無論最好、最壞還是平均情況，均爲 O(n²)。因爲需要兩層循環，外層循環 n 次，內層循環最多 n-1 次，總操作次數約爲 n(n-1)/2，即平方級。
空間複雜度：O(1)。僅需一個臨時變量用於交換，無需額外空間。

六、適用場景與優缺點¶

優點：
1. 算法簡單，邏輯清晰，易於理解和實現；
2. 交換次數最少（最多 n-1 次），適合對“交換成本”敏感的場景（如硬件資源有限時）；
3. 空間複雜度低，僅需常數空間。
缺點：
1. 時間複雜度高（O(n²)），不適合大規模數據排序；
2. 不穩定排序（例如，原數組中兩個相等元素的相對順序可能改變）。
適用場景：小規模數據排序、對交換次數敏感的場景（如嵌入式系統）。

總結¶

選擇排序是排序算法中的“入門級選手”，它以簡單的邏輯和最少的交換次數著稱。雖然時間複雜度較高，但在理解排序核心思想和處理小規模數據時，仍是絕佳的選擇。掌握選擇排序，能幫助我們更深入地理解排序算法的設計思路，爲後續學習更復雜的排序算法（如歸併排序、快速排序）打下基礎。