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;
}