# 排序數組所需的最小交換次數 > 原文： [https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/](https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/) 給定 **n** 個不同元素的數組，請找到對數組進行排序所需的最小交換次數。 **示例**： ``` Input : {4, 3, 2, 1} Output : 2 Explanation : Swap index 0 with 3 and 1 with 2 to form the sorted array {1, 2, 3, 4}. Input : {1, 5, 4, 3, 2} Output : 2 ``` 通過將問題可視化為圖形，可以輕松完成此操作。 如果第 i 個索引的元素必須存在于第 j 個索引中，則我們將有 **n 個**節點和一條從節點 **i** 指向節點 **j** 的邊。 排序后的數組。 ``` Graph for {4, 3, 2, 1} ``` 該圖現在將包含許多不相交的循環。 現在，具有 2 個節點的循環只需要進行 1 次交換即可達到正確的順序，類似地，具有 3 個節點的循環也只需進行 2 次交換即可。 ``` Graph for {4, 5, 2, 1, 5} ``` 因此， * ans = **Σ _{i = 1} ^k** （cycle_size – 1） 其中 **k** 是周期數 以下是該想法的實現。 ## C++ ```cpp // C++ program to find? minimum number of swaps // required to sort an array #include<bits/stdc++.h> using namespace std; // Function returns the minimum number of swaps // required to sort the array int minSwaps(int arr[], int n) { ????// Create an array of pairs where first ????// element is array element and second element ????// is position of first element ????pair<int, int> arrPos[n]; ????for (int i = 0; i < n; i++) ????{ ????????arrPos[i].first = arr[i]; ????????arrPos[i].second = i; ????} ????// Sort the array by array element values to ????// get right position of every element as second ????// element of pair. ????sort(arrPos, arrPos + n); ????// To keep track of visited elements. Initialize ????// all elements as not visited or false. ????vector<bool> vis(n, false); ????// Initialize result ????int ans = 0; ????// Traverse array elements ????for (int i = 0; i < n; i++) ????{ ????????// already swapped and corrected or ????????// already present at correct pos ????????if (vis[i] || arrPos[i].second == i) ????????????continue; ????????// find out the number of? node in ????????// this cycle and add in ans ????????int cycle_size = 0; ????????int j = i; ????????while (!vis[j]) ????????{ ????????????vis[j] = 1; ????????????// move to next node ????????????j = arrPos[j].second; ????????????cycle_size++; ????????} ????????// Update answer by adding current cycle.? ????????if (cycle_size > 0) ????????{ ????????????ans += (cycle_size - 1); ????????} ????} ????// Return result ????return ans; } // Driver program to test the above function int main() { ????int arr[] = {1, 5, 4, 3, 2}; ????int n = (sizeof(arr) / sizeof(int)); ????cout << minSwaps(arr, n); ????return 0; } ```