1 作用

置换环是用来求解数组排序元素间所需最小交换次数这类问题。

置换环思想：置换环将每个元素指向其排序后应在的位置，最终首位相连形成一个环（若数字在最终位置，则其自身成环），可知元素之间的交换只会在同一个环内进行，而每个环内的最小交换次数为

我们将所有环的交换次数加起来得到

其中\(cyclesize_i\)为环上元素数量。

最后化简公式得，排序所需最小交换次数为数组长度-环的个数。

图例：

其中环数为3，数组长度为6，所以最小交换次数为3

2 代码

代码通过计算环上元素数量 - 1实现：

//置换环
pair<int, int> arrpos[len];//一维记录数值，一维记录位置
for(int i = 0;i < len;i++){
    arrpos[i].first = tmp[i];
    arrpos[i].second = i;
}
//跑次数
sort(arrpos,arrpos + len);
vector<int> vis(len,0);
for(int i = 0;i < len;i++){
    int cycelsize = 0;
    //自环或者访问过
    if(vis[i] || arrpos[i].second == i) continue;
    int j = i;
    while(!vis[j]){
        vis[j] = 1;
        j = arrpos[j].second;
        cycelsize += 1;
    }
    if(cycelsize > 0){
        ans += (cycelsize - 1);
    }
}

3 例题

逐层排序二叉树所需的最少操作数目