View Code of Problem 126

#include<stdio.h>
struct inversion
{
	int t;
	int in;
} ;
int main()
{
	char DNA[110][60];
	int m,n;
	int i,j,k,inn;
	struct inversion inv[100],tmp;
	scanf("%d%d",&n,&m);/*读入数据*/
	for(i=0;i<m;i++)
	{
		scanf("%s",DNA[i]);
		inn=0;
		for(j=0;j<n-1;j++)
			for(k=j+1;k<n;k++)
				if(DNA[i][j]>DNA[i][k])
					inn++;
		/*记录逆序数*/
		inv[i].t=i;
		inv[i].in=inn;
	} 
	/*选择排序法*/
	for(i=0;i<m-1;i++)
	{
		k=i;
		for(j=i+1;j<m;j++)
			if(inv[j].in<inv[k].in)
				k=j;
		if(i!=k)
		{
			tmp=inv[i];
			inv[i]=inv[k];
			inv[k]=tmp;
		}
	}
	/*输出数据*/
	for(i=0;i<m;i++)
		printf("%s\n",DNA[inv[i].t]);
	return 0;
}