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.
Each input file contains one test case, which gives a positive N (≤) followed by a permutation sequence of {0, 1, ..., N−1}. All the numbers in a line are separated by a space.
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
10
3 5 7 2 6 4 9 0 8 1
9
1.N个数字排列整齐的条件是Position[X] == X；
2.N个数字的全排列（permutation）必定构成若干个闭环。
3.Swap(0, X)就相当于Swap(Position[0], Position[X])
0.规律2
如样例：
X 3 5 7 2 6 4 9 0 8 1
Position 0 1 2 3 4 5 6 7 8 9
Position[7] = 0; Position[0] = 3; Position[3] = 2; Position[2] = 7; Position[7] = 0 …………
1.由规律2 && 规律3容易得到，针对0的元素交换只能在包含0的闭环中进行。
如： 对于7-0-3-2-7闭环中，无论怎么交换，最后情况
Position[7] = 7;
Position[0] = 0;
Position[3] = 3;
Position[2] = 2。
2.所以如果排序序列中有多个环，就要让0进入不包含0的环，进入的方法也很简单：
Swap(Position[0], Postion[X]) where X is any member of any anther loop.
3.按照题意（4，0，2，1，3）交换顺序的提示，本题应该是贪心（greedy）算法的意思。
即每次Swap，把Position[0]对应的元素拉回原位。
如：
1.Position[0] = 3
2.Position[3] = 2;
3.Swap( Position[0], Position[3] )
Outcome:
Position[0] = 2;
Position[3] = 3; /*correct position*/
4. 按照贪心算法，可以简化步骤2，因为每次包含0的环在进行若干次Swap后所有元素均有序，
所以剩下的不包含0的环的元素有一个共同特点——即Position[X] !=X
步骤一、
根据说明3复位含0的闭环中的所有元素
步骤二、
查找仍在错误位置的X，交换(0,X)；若找不到则退出循环
步骤三、
Swap(0，X)，回步骤一
1.数组
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 const int MAXN = 1e5 + 1; 6 7 int Position[MAXN]; 8 void ZeroSort(int N); 9 10 int main() 11 { 12 int N, tmp; 13 scanf("%d", &N); 14 15 for (int i=0; i<N; i++) { 16 scanf("%d", &tmp); 17 Position[tmp] = i; 18 } 19 20 21 22 ZeroSort( N ); 23 24 25 return 0; 26 27 } 28 29 void ZeroSort(int N) 30 { 31 int P, PreZeroPos, cnt; 32 cnt = 0; 33 34 while (1) { 35 PreZeroPos = Position[0]; 36 37 if (Position[0] != 0) { 38 swap( Position[0], Position[Position[0] ] ); 39 } 40 else { 41 for (P=0; P<N; P++) if(Position[P] != P) break; 42 swap( Position[0], Position[P] ); 43 } 44 if (PreZeroPos == Position[0]) { 45 break; 46 } 47 cnt++; 48 } 49 50 printf("%d\n", cnt); 51 52 } 53
2.数组+std::set（内部实现是AVL树）
1 #include <cstdio> 2 #include <algorithm> 3 #include <set> 4 using namespace std; 5 const int MAXN = 1e5 + 1; 6 7 int Position[MAXN]; 8 9 10 11 void ZeroSort(int N, set<int> St); 12 13 14 int main() 15 { 16 int N, tmp; 17 set<int> St; 18 19 scanf("%d", &N); 20 21 for (int i=0; i<N; i++) { 22 scanf("%d", &tmp); 23 Position[tmp] = i; 24 if (Position[i] != i and i!=0) { 25 St.insert(i); 26 } 27 } 28 29 30 31 ZeroSort( N, St ); 32 33 return 0; 34 35 } 36 37 38 39 void ZeroSort(int N, set<int> St) 40 { 41 int PreZeroPos, cnt, X; 42 cnt = 0; 43 44 //O(N) 45 while (St.size() != 0) { 46 PreZeroPos = Position[0]; 47 48 if (PreZeroPos != 0) { 49 swap( Position[0], Position[ PreZeroPos ] ); 50 St.erase( St.find(PreZeroPos) ); 51 } 52 53 else { 54 X = *(St.begin()); 55 swap( Position[0], Position[X] ); 56 } 57 58 cnt++; 59 60 } 61 62 printf("%d\n", cnt); 63 64 } 65
（二）分析
Version1 超时
分析：
如何识别Position[X] != X，Version 1中扫描了整个数组,O(N)；
外面的大循环显然也是O(N)的，因为最坏情况下S要Swap N-1 次;
总的复杂度O(N^2)，N=1e5不可接受。
Version2 AC
分析：
1.步骤一、
复位X后删除MalPosSt中的元素，表示该元素已经复位。O(logN)
2.步骤二、
任选MalPosSt中元素，此处我选了*( MalPosSt.begin() )。 O(1)
3.步骤三、
O(1)
外面大循环O(N)，总的复杂度为O(NlogN）
10-排序6 Sort with Swap(0, i) (25 分)
原文：https://www.cnblogs.com/acoccus/p/10935774.html