1.题目要求只允许交换0和其他数值，最后得到一个排序的数组，求最小的交换次数。注意是交换0，而不是交换0这个位置上的值。譬如10567，swap(0,6)后得到16507.
2.用一个数组pos记录各个元素所在的位置
3.假设0所在的位置为i，那么正确的排序应该是i在位置i上，所以0应该和i交换，即0的位置和i的位置交换，swap(pos[0],pos[i])，又pos[0]=i，即0的位置在i上，所以swap(pos[0],pos[pos[0]])。
4.通过3中提到的，每次都把一个数换到正确的位置，步数最小。
5.可能还存在尚未结束，但是0已经在位置0上，此时进行交换，对排序没有帮助，于是我们需要把0和任意一个不符合pos[i]=i要求的数进行交换，然后再进行上述的步骤。
6.需要记录上次是哪个i不满足pos[i]=i的要求，这样才能AC，不然会超时（即每次都得从0搜索到n-1，会超时）。
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 (<=105) 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:
9
AC代码：
[c language=”++”]
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
int main(void)
{
int n;
cin >> n;
vector<int> num(n);
vector<int> pos(n);
int disorderPos = -1;//记录不合要求的第一个位置
for (int i = 0; i < n; i++)
{
int tmp;
scanf("%d", &tmp);
pos[tmp] = i;//记录tmp所在位置i
if (tmp != i&&disorderPos == -1) disorderPos = i;
}
int step = 0;
while (1)
{
if (pos[0] != 0)
{//把0所在的位置pos[0]=i换成数字i，此时数字i在位置pos[i]上，所以需要swap(pos[0], pos[pos[0]]);
swap(pos[0], pos[pos[0]]);
step++;
}
else
{
for (; disorderPos < pos.size(); disorderPos++)
if (pos[disorderPos] != disorderPos)//找出不合要求的数
break;
if (disorderPos == pos.size()) break;
swap(pos[0], pos[disorderPos]);
step++;
}
}
cout << step << endl;
return 0;
}
[/c]