最小交換次數排序：置換循環分解法 O(N) 解法詳解

給定一個包含 1‥N 的排列，允許任意兩元素交換，求將其排序為遞增序列所需的最少交換次數。本文揭示此問題的數學本質——置換循環分解，並給出 O(N) 時間、O(N) 空間的最優演算法。

核心洞察：置換與循環分解

目標陣列 [1, 2, ..., N] 滿足 a[i] == i+1。當前陣列可視為一個置換 π，其中 π(i) = a[i]。任意置換皆可唯一分解為若干不相交循環。一個長度為 k 的循環，僅需 k-1 次交換即可修正（每次交換將一個元素放到正確位置）。

最小交換總數 = Σ (循環長度 - 1) = N - 循環個數

演算法流程

1. 建立 visited[N] 標記陣列，初始全 false。
2. 遍歷 i = 0‥N-1：
   • 若 visited[i] 為真，跳過。
   • 否則從 i 出發追蹤循環：j = i; while (!visited[j]) { visited[j]=true; j = a[j]-1; }。
   • 統計該循環長度 len，累加 len - 1 到答案。

C++ 參考實作

#include <vector>
using namespace std;

int minSwaps(const vector<int>& a) {
    int n = a.size();
    vector<bool> vis(n, false);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        int len = 0, j = i;
        while (!vis[j]) {
            vis[j] = true;
            j = a[j] - 1;  // 元素值 - 1 = 正確索引
            ++len;
        }
        if (len > 1) ans += len - 1;  // 長度 1 的循環已就位
    }
    return ans;
}

範例驗證

為何非冒泡排序交換數？

冒泡排序交換相鄰元素，交換數等於逆序對數量，非最小交換數。本題允許「任意兩元素交換」，故利用循環分解可達到理論下界。

複雜度與擴充

• 時間：O(N) —— 每個元素僅被訪問一次。
• 空間：O(N) —— visited 陣列；若允許修改原陣列可壓縮至 O(1)。
• 擴充：若元素非 1‥N 連續整數，先做座標壓縮（排序+映射）即可套用同樣邏輯。

總結

最小交換排序問題的關鍵在於識別「置換循環」。掌握循環分解思維，不僅能秒殺此題，更能舉一反三解決最小交換使陣列有序、字串變換等同構問題。