归并排序 0MS
#include<iostream>
#include<fstream>
using namespace std;
typedef struct node{
   char str[51];
   int num;
}STR;
STR dna[101];
int tj,n,m;
void qsort(STR *a,int st,int ed)
{
    if (st>=ed)
    return;
    int i=st,j=ed;
    STR temp=a[i];
    while (i<j)
    {
       while (i<j&&a[j].num>temp.num)
       j--;
       if (i<j)
       a[i]=a[j];
       while (i<j&&a[i].num<=temp.num)
       i++;
       if (i<j)
       a[j]=a[i];
    }
    a[i]=temp;
    qsort(a,st,i-1);
    qsort(a,i+1,ed);
    return;
}
void combine(char *a,int st,int mid,int ed)
{
     char ch[101];
     memset(ch,0,sizeof(ch));
     int i=st,j=mid+1,k=0,l;
     while (i<=mid&&j<=ed)
     {
         if (a[i]>a[j])
         {
            ch[k++]=a[j++];
            tj+=(mid-i+1);
         }
         else
           ch[k++]=a[i++];
     }
     while(i<=mid)
     {ch[k]=a[i];i++;k++;}
     while(j<=ed)
     {ch[k]=a[j];j++;k++;}
     i=st;
     for (l=0;l<k;l++,i++)
     a[i]=ch[l];
}
void merge(char *a,int st,int ed)
{
     if (st>=ed)
     return;
     int mid=(st+ed)/2;
     merge(a,st,mid);
     merge(a,mid+1,ed);
     combine(a,st,mid,ed);
}
int main()
{
    ifstream infile;
    ofstream outfile;
    infile.open("in.txt",ios::in);
    outfile.open("out.txt",ios::out);
    int i,j;
    char temp[101];
    infile>>n>>m;
    for (i=0;i<m;i++)
    {
        infile>>dna[i].str;
        memset(temp,0,sizeof(temp));
        for (j=0;j<n;j++)
        temp[j]=dna[i].str[j];
        tj=0;
        merge(temp,0,n-1);
        dna[i].num=tj;
    }
    qsort(dna,0,m-1);
    for (i=0;i<m;i++)
    outfile<<dna[i].str<<endl;
    infile.close();
    outfile.close();
    return 0;
}

高手提供的O(n)求逆序对

#include<iostream>
using namespace std;
typedef struct node{
   char str[51];
   int num;
}STR;
STR dna[101];
int tj,n,m;
void qsort(STR *a,int st,int ed)
{
    if (st>=ed)
    return;
    int i=st,j=ed;
    STR temp=a[i];
    while (i<j)
    {
       while (i<j&&a[j].num>temp.num)
       j--;
       if (i<j)
       a[i]=a[j];
       while (i<j&&a[i].num<=temp.num)
       i++;
       if (i<j)
       a[j]=a[i];
    }
    a[i]=temp;
    qsort(a,st,i-1);
    qsort(a,i+1,ed);
    return;
}

int main()
{
    int i,j,a[4];
    char temp[101];
    cin>>n>>m;
    for (i=0;i<m;i++)
    {
        cin>>dna[i].str;
        memset(temp,0,sizeof(temp));
        tj=0;
        memset(a,0,sizeof(a));
        for (j=n-1;j>=0;j--)
        {
            switch (dna[i].str[j]){
                   case 'A':
                        a[1]++;
                        a[2]++;
                        a[3]++;
                        break;
                   case 'C':
                        a[2]++;
                        a[3]++;
                        tj+=a[1];
                        break;
                   case 'G':
                        a[3]++;
                        tj+=a[2];
                        break;
                   case 'T':
                        tj+=a[3];
                        }
        }
        dna[i].num=tj;
    }
    qsort(dna,0,m-1);
    for (i=0;i<m;i++)
    cout<<dna[i].str<<endl;
    return 0;
}