POJ-1007-DNA Sorting-求逆序数

之前看过这题道，由于当时对如何使用STL的sort还不熟悉，而自己又想偷懒，故没有做下去。今天看了《C++标准程序库》对sort有了一定的认识，便A了这道题。

经典的求逆序数的题，只是我是用暴力求解的。《算法导论》第二章的习题上面也有类似的题。看来还得研究下。

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

/*表示DNA的类*/
class DNA {
    public:
        string str; //串
        int inv; //逆序数
};

const int MAX = 100;
int getInverCount(string str); //求一个串的逆数的函数
bool cmp(const DNA& a, const DNA& b); //传入sort参数的比较函数

int main()
{
    DNA dnaArr[MAX];

    int n, m;
    cin >> n >> m;
    string str;
    for(int i = 0; i < m; i++) {
        cin >> str;
        dnaArr[i].str = str;
        dnaArr[i].inv = getInverCount(str);
    }

    //根据DNA的逆序数从小到大对DNA对象进行排序
    sort(dnaArr, dnaArr + m, cmp);

    for(int i = 0; i < m; ++i) {
        cout << dnaArr[i].inv << endl;
    }

    return 0;
}

/*暴力方法求逆数，时间复杂度为O(n^2)*/
int getInverCount(string str) {
    int count = 0;
    string::size_type i, j;
    for(i = 0; i != str.size(); i++) {
        for(j = i + 1; j != str.size(); j++) {
            if(str[j] < str[i])
                count++;
        }
    }

    return count;
}

/*逆序数从小到大排序*/
bool cmp(const DNA& a, const DNA& b) {
    return a.inv < b.inv;
}