(使用排序算法进行编程7.3.11)POJ 1007 DNA Sorting(使用冒泡排序算法来计算逆序对)

/* 
 * POJ_1007.cpp 
 * 
 *  Created on: 2013年11月4日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
#include <string>  
#include <cstring>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 105;  
struct DNA {  
    string str;  
    int num;  
} dnas[maxn];  
  
bool cmp(const DNA& a, const DNA& b) {  
    return a.num < b.num;  
}  
  
int main() {  
    int n, m;  
  
    while (scanf("%d%d", &n, &m) != EOF) {  
        int i;  
        for (i = 0; i < m; ++i) {  
            cin >> dnas[i].str;  
            dnas[i].num = 0;  
            int j, k;  
            for (k = 0; k < n; ++k) { //冒泡排序  
                for (j = k + 1; j < n; ++j) {  
                    if (dnas[i].str[k] > dnas[i].str[j]) {  
                        dnas[i].num++; //逆序对数+1  
                    }  
                }  
            }  
  
        }  
  
        sort(dnas,dnas+m,cmp);  
  
        for(i = 0 ; i < m ; ++i){  
            cout<<dnas[i].str<<endl;  
        }  
    }  
  
    return 0;  
}