/*===================================== 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
思路：
用结构体数组存储每一个字符串和字符串的逆序对个数。
流程：
循环：输入字符串——统计逆序对
排序
输出 ======================================*/
1 #include<stdio.h> 2 struct DNA 3 { 4 char a[50];//一个基因序列 5 int num;//本基因序列的逆序对个数 6 }; 7 int niXuDui(struct DNA d,int len);//统计DNA序列变量d的逆序对个数 8 int main() 9 { 10 struct DNA d[100],t; 11 int n,m,i,j,flag; 12 freopen("5.in","r",stdin); 13 scanf("%d%d",&n,&m); 14 for(i=0;i<m;i++) 15 { 16 scanf("%s",d[i].a); 17 d[i].num=niXuDui(d[i],n); 18 } 19 20 for(i=1;i<m;i++) 21 { 22 flag=1; 23 for(j=0;j<m-i;j++) 24 { 25 if(d[j].num>d[j+1].num) 26 { 27 flag=0; 28 t=d[j]; 29 d[j]=d[j+1]; 30 d[j+1]=t; 31 } 32 } 33 if(flag) break; //if(flag==1) break; 34 } 35 for(i=0;i<m;i++) 36 { 37 printf("%s\n",d[i].a); 38 } 39 return 0; 40 } 41 int niXuDui(struct DNA d,int len)//统计DNA序列变量d的逆序对个数 42 { 43 int ans=0,i,j; 44 for(i=0;i<len;i++) 45 { 46 for(j=i+1;j<len;j++) 47 { 48 if(d.a[j]<d.a[i]) ans++; 49 } 50 } 51 return ans; 52 }
Openjudge计算概论-DNA排序,布布扣,bubuko.com
原文：http://www.cnblogs.com/huashanqingzhu/p/3575491.html
