1093.DNA排序 SDNUOJ 1093

Description
逆序数可以用来是描述一个序列混乱成度的量。例如，“DAABEC”的逆序数为5，其中D大于它右边的4个数，E大于它右边的1个数，4+1=5；又例如“ZWQM”的逆序数为3+2+1+0=6。
现在有许多长度一样的字符串，每个字符串里面只会出现四种字母（A,T,G,C）。你现在被要求编写程序将这些字符串按照他们的逆序数进行排序
Input
第一行包括两个正整数，第一个正整数N给出了字符串的长度，第二个正整数M给出了字符串的数量。（1<=N，M<=100）
接下来M行每行一个长度为N的字符串，只包含A,T,G,C四种字母。
Output
将输入的字符串按照其逆序数进行排序，如果两个字符串的逆序数相等，则按照输入中两者的先后顺序进行排列。
Sample Input
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
Sample Output
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
    char s[105];
    int sum;
} a[105];

void f(node * a, int n)
{
    for(int i = 0; i < n - 1; ++i)///冒泡排序n个元素外循环n-1次
        for(int j = 0; j < n - i - 1; ++j)
            if(a[j].sum > a[j + 1].sum)///交换字符串的同时交换逆序数
            {
                char temp[105];
                int tem;
                strcpy(temp, a[j].s);
                tem = a[j].sum;
                strcpy(a[j].s, a[j + 1].s);
                a[j].sum = a[j + 1].sum;
                strcpy(a[j + 1].s, temp);
                a[j + 1].sum = tem;
            }
    return ;
}

int main()
{
    int m, n;
    while(cin >> m >> n)
    {
        for(int i = 0; i < n; ++i)
        {
            cin >> a[i].s;
            int len = strlen(a[i].s);
            for(int j = 0; j < len; ++j )
                for(int k = j + 1; k < len; ++k)
                {
                    if(a[i].s[k] < a[i].s[j])
                        a[i].sum++;
                }
        }
        f(a, n);
        for(int i = 0 ; i < n; ++i)
            cout << a[i].s << '\n';
    }
    return 0;
}