#2 TLE 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,a[10005],b[10005],c[10005],ans=0;
	bool ck=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=c[i]=a[i];
	}
	sort(b+1,b+1+n);
	sort(c+1,c+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=c[i])
		{
			ck=0;
			break;
		}
	}
	if(ck)
	{
		cout<<n/2;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			for(int j=i;j<=n;j++)
			{
				if(a[j]==b[i]) 
				{
					swap(a[i],a[j]);
					break;
				}
			}
			ans++;
		}
	}
	cout<<ans;
}

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,a[10005],b[10005],c[10005],ans=0;
	bool ck=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=c[i]=a[i];
	}
	sort(b+1,b+1+n);
	sort(c+1,c+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=c[i])
		{
			ck=0;
			break;
		}
	}
	if(ck)
	{
		cout<<n/2;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			for(int j=n;j>=i;j--)
			{
				if(a[j]==b[i]) 
				{
					swap(a[i],a[j]);
					break;
				}
			}
			ans++;
		}
	}
	cout<<ans;
}

时间复杂度同为 $O(n^2)$， 为何结果不一样？
（不打 cmp 函数的原因是怕有人直接抄代码，空间也被我手动改小了）
（应该可以被 hack 吧）（悲）