接下来就是m行，每一行包含一个长度为n的字符串。
输出：
输出是输入串的列表，按有序性从高往低排序。
因为两个串可以相等，则按照它们原来的顺序输出。
样例输入：
106
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
样例输出：
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
3算法分析
3.1计算字符串的逆序数
本题中，由于字符串中字符的范围是确定的，只有A、C、G、T，所以可以在O（n）内求出逆序数方法是：
count作为记录逆序数的大小，初始化为0。
从后向前插入字符，以下四个参数分别代表如果在左边加上A、C、G、T，逆序数会加上多少，left_A、left_C、left_G、left_T。
首先四个参数都初始化为0，然后从后向前插入字符，如果插入的是A：
以后在前面插入C、G、T，逆序数都会增加，所以：
left_C++；left_G++；left_T++;如果插入的是C：
逆序数加上left_C,以后在前面插入G、T，逆序数都会增加，所以：
left_G++；left_T++；如果插入的是G：
逆序数加上left_G；以后在前面插入T，逆序数都会增加，所以：
left_T++；如果插入的是T：
逆序数加上left_T,以后在前面插入字符，逆序数都不会增加。
因此有代码：
for（i=length-1;i>=0;i--）
{//str是要计算逆序数的字符串，count为逆序数
a=str[i];
switch（a）
{
case'A':
left_C++;
left_G++;
left_T++;
break;
case'C':
left_G++;
left_T++;
count+=left_C;
break;
case'G':
left_T++;
count+=left_G;
break;
case'T':
count+=left_T;
break;
}
}
returncount;
3.2计数排序
将所有字符串的逆序数存入数组A，对这些数进行排序。
因为待排序的元素是位于0到k之间的整数，因此可以利用计数排序实现，同时能很方便地输出DNA串。
算法的基本思想是:
统计A中元素的值的集合,以A中元素的值为索引,将值的个数填写到中间数组C的对应处。
对C从头开始自累加,这样C中存储的就是,当输入数组A中的值为当前索引时，它前面的元素数量（包含重复元素）。
将C依次输出到输出数组中。
本题中，算法描述如下：
max_element=0；
for（i=1;i<=m;i++）
{
temp=A[i];
if（temp>max_element）
max_element=temp;
C[temp]++;
}
for（i=0;i<=max_element;i++）
C[i+1]+=C[i];
for（i=m;i>=1;i--）
{
B[C[A[i]]]=i;
C[A[i]]--;
}
4程序流程图
图1程序主流程图
图2reverse（）函数的流程图
5程序源码
#include
#include
#defineMAX_SIZE101
#defineMAX_NUM2500
//针对该题求逆序数的方法，适用于范围确定的情况
intreverse（char*str,intlength）
{
//至后向前插入字符，以下四个参数分别代表如果在左边加上ACGT
//逆序数会加上多少
intleft_A=0;
intleft_C=0;
intleft_G=0;
intleft_T=0;
inti,count=0;
chara;
for（i=length-1;i>=0;i--）
{
a=str[i];
switch（a）
{
case'A':
left_C++;
left_G++;
left_T++;
break;
case'C':
left_G++;
left_T++;
count+=left_C;
break;
case'G':
left_T++;
count+=left_G;
break;
case'T':
count+=left_T;
break;
}
}
returncount;
}
main（）
{
charDNA[101][51];
inti,A[101],length,m;
//计数排序,A[]为初始数组,下标从1开始,B[]为结果数组,下标从1开始,
//C[]为辅助数组
intC[MAX_NUM],max_element=0;
intB[MAX_SIZE],temp;
scanf（"%d%d",&length,&m）;
for（i=1;i<=m;i++）
{
scanf（"%s",DNA[i]）;
A[i]=reverse（DNA[i],length）;
}
memset（C,0,4*MAX_NUM）;
for（i=1;i<=m;i++）
{
temp=A[i];
if（temp>max_element）
max_element=temp;
C[temp]++;
}
for（i=0;i<=max_element;i++）
C[i+1]+=C[i];
for（i=m;i>=1;i--）
{
B[C[A[i]]]=i;
C[A[i]]--;
}
//按顺序输出字符串
for（i=1;i<=m;i++）
printf（"%s\n",DNA[B[i]]）;
}
6试算截屏图
图3程序运行截图
7分析与总结
这两个算法都能在Ｏ（n）的时间范围内实现。
一般采用归并排序的方法求逆序数，但本题中，由于字符串中字符的个数是确定，因此采用3.2的方法求解更加简洁、易于理解。
同时由于得到的待排序元素的特殊性，采用计数排序进行排序。
同时题中指明若两个串相等按照它们原来的顺序输出，而计数排序是一种稳定的排序方法，正好满足要求。
8参考文献
[1]李文新、郭炜、余华山.程序设计导引及在线实践[M].北京：
清华大学出版社
[2]谭浩强.C程序设计[M].北京：
清华大学出版社，2005.
[3]严蔚敏，吴伟民.数据结构[M].北京:
清华大学出版社，1996.
[4]钟珞.计算机科学导论[M].武汉：
武汉理工大学出版社.
[5]张富.C及C++程序设计[M].北京：
人民邮电出版社.
本科生课程设计成绩评定表
班级：
姓名：
学号：
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
10
6
设计验收
10
总得分/等级
评语：
注：
最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
2013年7月12日
升级会员 