#include<stdio.h>           //这是一个O(N)的解法，以前的那个优质解法的帖子中的算法是O(N^2)的，实际跑出来，我的解法16MS，那个解法32MS，说明这个优化还算可以的。        
#include<stdlib.h>                     

int cmp(const void * a, const void * b)  
{
	return((*(int*)a-*(int*)b));
}

int measure(char *str,int len)
{
	int tmp_C=0,tmp_G=0,tmp_T=0;          
int front_C=0,front_G=0,front_T=0;
int total_C=0,total_G=0,total_T=0;
	int exist_C=0,exist_G=0,exist_T=0;
	for(int i=len-1;i>=0;i--)
	{
		switch (str[i])
		{
			case 'A':
				tmp_C++;
				tmp_G++;
				tmp_T++;
				break;
			case 'C':
				exist_C=1;
				tmp_G++;
				tmp_T++;
				front_C+=tmp_C;
				total_C+=front_C;
				tmp_C=0;
				break;
			case 'G':
				exist_G=1;
				tmp_T++;
				front_G+=tmp_G;
				total_G+=front_G;
				tmp_G=0;
				break;
			case 'T':
				exist_T=1;
				front_T+=tmp_T;
				total_T+=front_T;
				tmp_T=0;
				break;
			default:
				printf("Error:illegal character!");
		}
	}
	return exist_C*total_C+exist_G*total_G+exist_T*total_T;
}

int main()
{
	int str_len,str_num;
	scanf("%d %d",&str_len,&str_num);
	char (*p)[str_len+1]=(char(*)[str_len+1])malloc(sizeof(char)*(str_len+1)*str_num);
	int *result=(int *)malloc(sizeof(int)*str_num);
	for(int i=0;i<str_num;i++)
	{
		scanf("%s",p[i]);
		result[i]=measure(p[i],str_len)*1000+i;        //秩与下标的绑定
	};
	qsort(result,str_num,sizeof(int),cmp);
	for(int i=0;i<str_num;i++)
		printf("%s\n",p[result[i]%1000]);
	free(p);
	free(result);
	return 0;
}
/*此代码中秩绑定的使用以及函数指针的使用，都是借鉴的以前某位大神的优质算法那个帖子中的，它们让代码更简洁，更漂亮，在此谢谢那位大神。我的代码中，大量使用了case语句，我感觉很丑陋，想到解决办法的请协助改进，谢谢。*/

• Re:一个O(N)复杂度的解法，欢迎评论 (1744) gazi3616 2015-05-07 17:02:25
• Re:一个O(N)复杂度的解法，欢迎评论 (377) wwylele 2015-09-23 15:06:58
• Re:一个O(N)复杂度的解法，欢迎评论 (1744) Zdoujiang 2016-04-01 09:21:35