Q:DNA排序
总时间限制:1000ms内存限制:65536kB
描述
给出一系列基因序列，由A,C,G,T四种字符组成。对于每一个序列，定义其逆序对如下：
序列中任意一对字符X和Y，若Y在X的右边（不一定相邻）且Y < X，则称X和Y为一个逆序对。
例如GAC这个序列，其中GC,GA都是逆序对。
一个序列的逆序对越多，则认为其"无序度"越高。你的任务是将基因按照无序度从小到大的顺序排序，如果存在无序度相同的序列，则按照原始输入顺序输出。
输入首先是基因序列的长度n(0 < n <= 50)和基因序列的个数m ( 0 < m <= 100).
然后依次是这m个基因序列.输出输出排序后的m个基因序列。样例输入
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
样例输出CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA
S：
#include <stdio.h>
struct DNA
{
char order[50];//基因序列
int num;//逆序对总数
} ;
int sum(char D[],int len);//子函数用于统计逆序对总数
int main()
{
struct DNA a[101],temp;
int n,m;//m个序列，长度即len为n
int i,j;
//freopen("2.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%s",a[i].order);
a[i].num=sum(a[i].order,n);
}
for(i=0;i<m-1;i++)
{
for(j=i;j>=0;j--)
{
if(a[j].num>a[j+1].num)
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<m;i++)
{
puts(a[i].order);
}
return 0;
}
int sum(char D[],int len)//子函数用于统计逆序对总数
{
int i,j;
int all=0;
for(i=0;i<len-1;i++)
{
for(j=i+1;j<len;j++)
{
if(D[i]>D[j])
all++;
}
}
return all;
}