B1067 Sort with Swap(0, i) (25分)
没调整完毕时，首位是0时，就把0和后面的没归位的第一位数字换，
首位不是0时，就把0和0所在位置的数去交换
每交换一次，步数加1
- 正解：
a[0]=0的时候，需要从头往后找第一个a[i]!=i的时候，重复了许多次从头往后找的操作，因为前一次已经能保证，到该数之前的都是a[i]=i了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=100001;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=633;
int main()
{
int a[MAX];
int n,m=0;
scanf("%d",&n);
int left=n-1;//存放除0以外的不在自己位上的个数
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
a[x]=i;
if(x==i&&x!=0)
left--;
}
int i=1;
while(left>0)
{
if(a[0]==0)//起始位置是否是0
{
while(i<n)
{
if(a[i]!=i)
{
swap(a[0],a[i]);
m++;
break;
}
i++;
}
}
while(a[0]!=0)
{
swap(a[0],a[a[0]]);
m++;
left--;
}
}
printf("%d\n",m);
return 0;
}
