poj 1007 DNA Sorting【逆序对】

终于可以说：没有那么水了（虽然还是很水）。。。。。。

关于逆序数的题目，开始用塑料的冒泡排序一直WA，后来自己写一个，终于过了，要求是稳定的！！！！！！！

AC的代码：

#include <stdio.h>
#include <string.h>

char DNA[105][55];		//输入原DNA序列
int visit[105];

int Inversion(int nTh,int len)
{
	int i,j,count=0;
	for(i=0;i<len;i++)
		for(j=i;j<len;j++)
			if(DNA[nTh][i]>DNA[nTh][j])
				count++;

	return count;
}

int main()
{
	//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
	int inverNum[102];		//对应每个数列的逆序数
	int n;
	int m;

	scanf("%d%d",&n,&m);
	
	int i,j;
	for(i=0;i<m;i++)
	{
		scanf("%s",DNA[i]);
		inverNum[i]=Inversion(i,n);		//传入排位第i个的DNA序列，和序列长度

		//test  OK
		//printf("逆序数为：%d\n",inverNum[i]);
	}

	//每次都找到inverNum最小的序列打印，一定是稳定的
	int min;
	int pos;
	for(i=0;i<m;i++)
	{
		min=1000;	//开始放min为一个很大的数
		for(j=0;j<m;j++)
			if(visit[j]==0 && min>inverNum[j])
			{
				min=inverNum[j];
				pos=j;
			}

		visit[pos]=1;	//标记被访问过了
		printf("%s\n",DNA[pos]);
	}
	
	return 0;
}

WA 2次的代码：

#include <stdio.h>
#include <string.h>

char DNA[105][55];		//输入原DNA序列

int Inversion(int nTh,int len)
{
	int i,j,count=0;
	for(i=0;i<len;i++)
		for(j=i;j<len;j++)
			if(DNA[nTh][i]>DNA[nTh][j])
				count++;

	return count;
}

int main()
{
	//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
	int inverNum[102];		//对应每个数列的逆序数
	int n;
	int m;

	scanf("%d%d",&n,&m);
	
	int i,j;
	for(i=0;i<m;i++)
	{
		scanf("%s",DNA[i]);
		inverNum[i]=Inversion(i,n);		//传入排位第i个的DNA序列，和序列长度

		//test  OK
		//printf("逆序数为：%d\n",inverNum[i]);
	}

	//直接用冒泡排序（稳定的）
	char tmpN,temp[55];
	for(i=0;i<m;i++)
		for(j=i;j<m;j++)
			if(inverNum[i]>=inverNum[j])
			{
				//交换逆序数
				tmpN=inverNum[j];
				inverNum[j]=inverNum[i];
				inverNum[i]=tmpN;

				//交换DNA序列
				strcpy(temp,DNA[j]);
				strcpy(DNA[j],DNA[i]);
				strcpy(DNA[i],temp);
			}

	for(i=0;i<m;i++)
		printf("%s\n",DNA[i]);
	
	return 0;
}

题目大意：

     序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如：在单词序列“DAABEC'”中，因为D大于右边四个单词，E大于C，所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1（E与D）——近似排序，而序列``ZWQM'' 逆序数为6（它是已排序序列的反序）。

     你的任务是分类DNA字符串（只有ACGT四个字符）。但是你分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。

输入：

第一行包含两个数：一个正整数n（0<n<=50）表示字符串长度，一个正整数m（0<m<=100）表示字符串个数。接下来m行，每行一个长度为n的字符串。

输出：

输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。

样例输入：

10 6

AACATGAAGG

TTTTGGCCAA

TTTGGCCAAA

GATCAGATTT

CCCGGGGGGA

ATCGATGCAT

样例输出:

CCCGGGGGGA

AACATGAAGG

GATCAGATTT

ATCGATGCAT

TTTTGGCCAA

TTTGGCCAAA

大致题意：

输入m个长度为n的DNA序列，把他们按照逆序数从小到大稳定排序输出。

PS:“稳定排序”就是当序列中出现A1==A2时，排序前后A1与A2的相对位置不发生改变。