10-排序6 Sort with Swap(0, i) (25point(s))

Given any permutation of the numbers {0, 1, 2,..., N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}

Swap(0, 3) => {4, 1, 2, 3, 0}

Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (≤10^5) followed by a permutation sequence of {0, 1, ..., N−1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10

3 5 7 2 6 4 9 0 8 1

Sample Output:

N 个数字的排列由若干个独立的环构成。每一次都是和 0 做 swap，如果这个环里面有 0，长度是 count，那么每次都找和 0 值这个元素的下标相同的元素，做一次 swap。对于这个环本来就有 0，只需要做 count - 1 次 swap。若这个环里面没有 0，就要把 0 先 swap 进去，然后再归位所以比环里有 0 的多 2 次，需要 count + 1 次 swap。如果 count == 0 那这个元素不用和谁做 swap。

#include <stdio.h>

#define N 100000

/* 每次都和 0 做 swap，一次归位一个数字 */

int main(int argc, char const *argv[])

{

    int a[N];

    int visited[N] = {0};

    int n, i;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {

        scanf("%d", &a[i]);

    }

    int sum = 0;      /* 总共需要多少次 swap */

    for (i = 0; i < n; i++) {

        if (!visited[i]) {

            visited[i] = 1;

            int index = i;

            int count = 0;  /* 环的元素个数，0 个不用做 swap */

            int next;

            while (a[index] != index) {

                visited[index] = 1;

                count++;

                next = a[index];

                a[index] = index;

                index = next;

            }

            if (count != 0) {

                sum = index == 0 ? sum + count - 1 : sum + count + 1;

            }

            // printf("index = %d, count = %d\n", index, count);

        }

    }

    printf("%d\n", sum);

    return 0;

}