合成有序数组最少交换次数（可交换不相邻）

先附上本题思路来源 https://blog.csdn.net/gettogetto/article/details/69389810

有点类似与并查集
举个例子1 4 2 3
4 2 3会形成一个循环节，对于这种循环节来说，最少需要循环节内元素个数-1次交换

故代码如下

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    int def;
    friend bool operator <(Node& a,Node& b){
        return a.val<b.val;
    }
}a[100005];
bool vis[100005];
int n,k,t;
int ans;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    n=read();
    int sum=0;
    for(int i=0;i<n;i++){
        a[i].val=read();
        a[i].def=i;
    }
    ans=0;
    sort(a,a+n);

    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        if(i!=a[i].def&&!vis[i]){//当发现交换过次序同时没有归入哪个循环节
            int k=i;
            int g=0;
            while(!vis[k])//查找该循环节所有元素
            {
                g++;
                vis[k]=1;
                k=a[k].def;

            }
            ans+=g-1;//循环节内元素个数-1
        }
    }


    cout<<ans<<endl;    
}