贪心。
若 0 的不在它的位置，那么 0 占的那个元素的位置，就和那个元素交换。
若 0 在它的位置，找一个没有归位的元素与 0 交换。
#include<bits/stdc++.h>
using namespace std;
int arr[100005];
int main()
{
int i,n,x,cnt=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&x);
arr[x]=i;
}
for(i=1;i<n;i++)
{
if(i!=arr[i])
{
while(arr[0]!=0)
{
swap(arr[0],arr[arr[0]]);
cnt++;
}
if(i!=arr[i])
{
swap(arr[0],arr[i]);
cnt++;
}
}
}
printf("%d",cnt);
system("pause");
return 0;
}
PAT (Advanced Level) 1067 Sort with Swap(0, i)
原文：https://www.cnblogs.com/VividBinGo/p/12222708.html