在C ++中对数组排序所需的最小交换次数
问题陈述
给定一个由N个不同元素组成的数组，请找到对数组进行排序所需的最小交换次数
示例
如果array为{4，2，1，3}，则需要2次交换
将arr[0]与arr[2]交换
用arr[3]交换arr[2]
算法
1. 在C ++中创建一对向量，其中第一个元素为数组值，第二个元素为数组索引。 2. 根据配对的第一个元素对配对的向量进行排序。 3. 遍历向量并检查与值映射的索引是否正确，如果不正确，则继续交换直到元素正确放置并继续计算交换次数。
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
vector<pair<int, int>> vec(n);
for (int i = 0; i < n; ++i) {
vec[i].first = arr[i];
vec[i].second = i;
}
sort(vec.begin(), vec.end());
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (vec[i].second == i) {
continue;
}
swap(vec[i].first,vec[vec[i].second].first);
swap(vec[i].second,vec[vec[i].second].second);
if (i != vec[i].second) {
--i;
}
++cnt;
}
return cnt;
}
int main() {
int arr[] = {4, 2, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swaps = " << getMinSwaps(arr, n) <<
endl;
return 0;
}当您编译并执行上述程序时。它产生以下输出
输出结果
Minimum swaps = 2