如何统计列表重排的元素交换次数？Linq实现方案探讨

嘿，要算出排序所需的最少交换次数，最靠谱的方法是分析原数组和目标有序数组之间的循环置换关系，原理其实很好懂：

• 如果元素已经在它该待的位置，那就是个长度为1的小循环，完全不用交换；
• 要是碰到一串元素互相“占位置”——比如A该去B的位置，B该去C的位置，C又该去A的位置——这就是个长度为k的循环，搞定这个循环只需要k-1次交换；
• 最后把所有循环的(k-1)加起来，就是总交换次数，也等价于「数组总元素数减去循环的总数」。

拿你的例子来说：
原数组：{1, 7, 4, 9, 5}
排序后数组：{1, 4, 5, 7, 9}

对应位置的映射关系：

• 索引0的1本来就在正确位置 → 单独一个小循环[0]
• 索引1的7该去索引4的位置，索引4的5该去索引2的位置，索引2的4该去索引1的位置 → 形成一个循环[1→2→4→1]（长度3）
• 索引3的9也在正确位置 → 小循环[3]

总交换次数就是(3-1)+0+0=2，和你给的示例结果完全对上。

下面是具体代码，其中Linq主要用来快速构建元素到目标索引的映射，逻辑清晰还省事儿：

基础实现（把逻辑讲得明明白白） #

public static int CountMinSwaps(int[] arr)
{
    int n = arr.Length;
    // 先拿到排序后的数组，再用Linq把每个元素和它的目标索引绑定成字典
    var sortedArr = arr.OrderBy(x => x).ToArray();
    var elementToTargetIndex = sortedArr
        .Select((value, index) => new { Value = value, Index = index })
        .ToDictionary(item => item.Value, item => item.Index);
    
    bool[] visited = new bool[n];
    int swapCount = 0;

    for (int i = 0; i < n; i++)
    {
        // 已经访问过或者元素在正确位置，直接跳过
        if (visited[i] || elementToTargetIndex[arr[i]] == i)
            continue;

        // 遍历当前这个循环，统计长度
        int cycleLength = 0;
        int currentIndex = i;
        while (!visited[currentIndex])
        {
            visited[currentIndex] = true;
            // 跳到当前元素应该去的目标位置
            currentIndex = elementToTargetIndex[arr[currentIndex]];
            cycleLength++;
        }

        // 循环长度大于1的时候，交换次数加(长度-1)
        if (cycleLength > 1)
            swapCount += cycleLength - 1;
    }

    return swapCount;
}

调用示例 #

int[] inputArr = {1,7,4,9,5};
int minSwaps = CountMinSwaps(inputArr);
Console.WriteLine(minSwaps); // 输出2

关于Linq的说明 #

上面的代码里已经用Linq处理了排序和字典映射的部分，这也是Linq最擅长的场景——快速做数据转换和查询。不过核心的循环遍历还是用普通for/while循环更合适，因为Linq不太适合带状态（比如标记已访问）的迭代操作。

另外要提一句：如果你的数组里有重复元素，上面的字典写法会报错（因为重复键），这时候得改成用队列存储每个值的所有目标索引，按需取用。不过你的例子里元素都是唯一的，所以这个代码直接能用～

内容的提问来源于stack exchange，提问作者Nishanth Suraj