首先读入数组，将数组和排好序的数组进行比较，nij表示应该在i的地方放置的是j的个数。
先将1放入应该在的位置，需要n12+n13次交换，然后将3放入应该在的位置，注意，n13中一些3被交换到2或者在处理1的时候已经交换到3，所以交换3就是n23+max(0,n13-n31).
/*
ID:Ryan
PROG:sort3
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");
int main()
{
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");
int a[1001];
int nn[4]={0,0,0,0};
int n13=0,n23=0,n12=0,n31=0,n32=0,n21=0;
int i,sum=0,n;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i];
nn[a[i]]++;
}
for(i=1;i<=nn[1];i++)
{
if(a[i]==2) n12++;
if(a[i]==3) n13++;
}
for(i=nn[1]+1;i<=nn[1]+nn[2];i++)
{
if(a[i]== 1) n21++;
if(a[i]== 3) n23++;
}
for(i=nn[1]+nn[2]+1;i<=n;i++)
{
if(a[i]== 1) n31++;
if(a[i]== 2) n32++;
}
int t;
fout<<n21+n31+n23+max(0,n13-n31)<<endl;
//system("PAUSE");
return 0;
}