对一个没有重复的数组进行排序的最小交换次数。

Question

我想找一个数组的最小交换次数来排序。(保证数组没有重复。)我找到了一个帖子，基本上是用一个图来实现的。计算为一个序列排序的最小交换次数。

但我想知道是否也可以通过运行选择排序并计算交换次数来实现。(见下面的代码。)这种方法正确吗？还是有一种情况下，它会给出错误的结果？

int minSwaps(int[] A, int n) {
    int numSwaps = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            numSwaps++;
            int temp = A[minIndex];
            A[minIndex] = A[i];
            A[i] = temp;
        }
    }
    return numSwaps;
}

Answer 1

你的方法是正确的。正如维基百科 解释:

选择排序与其他排序算法不同的一点是，它使交换的次数尽可能减少。n - 在最坏的情况下为1。

这一点即使在数组 可以 包含重复的内容。

事实上，您的方法只是在以下方法的一个特例 你所指向的问题. 这个问题其实并没有 使用 图；答案只是用图论来试图证明这种方法是可行的。所以那里的论点也同样适用于你的方法。

也就是说，你的确切方法需要O(n²)的比较，而这种方法的其他变体只需O(n 原木 n)的时间。只有你才能决定你的变体的简单性是否值得更大的时间复杂性。