poj1007 DNA排序

题目大概意思：给出一系列DNA字母串（高中生物知识可知仅含ACTG四个字母），以逆序数作为评判标准，从好到坏排序。那什么是逆序数？举个例子“ACG”，从左往右任何一个字母均比之前的大，故无逆序，逆序数为0。又比如在单词序列“DAABEC'”中，因为D大于右边四个单词，E大于C，所以计算结果为5。

输入：第一行包含两个数：一个正整数n（0 < n <= 50，字符串长度）一个正整数m（0 < m <= 100，字符串数量），接下来m行为具体字符串

输出：输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。

//
//  main.cpp
//  T1007
//
//  Created by 小哲 on 16/9/28.
//  Copyright © 2016年 小哲. All rights reserved.
//

#include <iostream>
using namespace std;


struct  DNAStruct
{
    char *dna;
    int value;
};
int l,n;
DNAStruct dnaArray[100];

DNAStruct GetValue(char *ch)
{
    int a=0;
    int c=0;
    int g=0;
    DNAStruct d;
    d.dna=ch;
    d.value=0;
    for (int i=l-1; i>=0; i--) {
        switch (ch[i]) {
            case 'A':
                a++;
                break;
            case 'C':
                c++;
                d.value=d.value+a;
                break;
            case 'G':
                g++;
                d.value=d.value+a+c;
                break;
            case 'T':
                d.value=d.value+a+c+g;
                break;
            default:
                break;
        }
    }
    return d;
}

void BSort()
{
    bool flag;
    for (int i=0; i<n-1; i++) {
        flag=true;
        for (int j=n-1;j>i ; j--) {
            if (dnaArray[j].value<dnaArray[j-1].value) {
                DNAStruct temp=dnaArray[j-1];
                dnaArray[j-1]=dnaArray[j];
                dnaArray[j]=temp;
                flag=false;
            }
        }
        if (flag) {
            break;
        }
    }
}


int main() {
    cin>>l>>n;
    for (int k=0; k<n; k++) {
        char *ch=new char[l];
        cin>>ch;
        dnaArray[k]=GetValue(ch);
    }
    BSort();
    for (int i=0; i<n; i++) {
        cout<<dnaArray[i].dna<<endl;
    }
    return 0;
}