归并排序

归并排序

归并排序的时间复杂度为O(N*log2N)

思路（递归）：
1.左边排好序
2.右边排好序
3.合并到一起使得整体有序

class MergeSort
{
public:
    void myMergeSort(vector<int>& v)
    {
        if (v.size() < 2)
            return;
        int L = 0;
        int R = v.size()-1;
        process(v, L,R);
    }
    void process(vector<int>& v, int L,int R)
    {
        if (L == R)
            return;
        else
        {
            int M = (L + R) / 2;
            process(v, L, M);
            process(v, M + 1, R);
            merge(v, L, M, R);
        }
    }
    void merge(vector<int>& v, int L, int M, int R)
    {
        vector<int> v2;
        int i = L;
        int j = M + 1;
        while(i <= M&&j <= R)
        {
            if (v[i] < v[j])
            {
                v2.push_back(v[i]);
                i++;
            }
            else
            {
                v2.push_back(v[j]);
                j++;
            }
        }
            while (j <= R)
            {
                v2.push_back(v[j++]);
            }
            while (i <= M)
            {
                v2.push_back(v[i++]);
            }
        for (i = 0; i <v2.size(); i++)
        {
            v[i+L]= v2[i];
        }
    }

};
void test04(vector<int> &v)
{
    MergeSort m;
    m.myMergeSort(v);
}

归并排序的应用

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
思路：在归并排序的Merge过程中进行小和的计数（谁小拷贝谁，相等先拷贝右边；左边小的时候就算右边有几个比它大，就有几个它当小和）
对于每一个数右边有几个比它大就产生了几个它当小和

class MergeSort
{
public:
    int smallSum(vector<int>& v)
    {
        if (v.size() < 2)
            return 0;
        int L = 0;
        int R = v.size() - 1;
        return process(v, L, R);
    }
    int process(vector<int>& v, int L, int R)
    {
        if (L == R)
            return 0;
        else
        {
            int M = (L + R) / 2;
            return process(v, L, M)+process(v, M + 1, R)+merge(v, L, M, R);
        }
    }
    int merge(vector<int>& v, int L, int M, int R)
    {
        int res=0;
        vector<int> v2;
        int i = L;
        int j = M + 1;
        while (i <= M && j <= R)
        {
            if (v[i] < v[j])
            {
                v2.push_back(v[i]);
                res += v[i] * (R - j + 1);
                i++;
            }
            else
            {
                v2.push_back(v[j]);
                j++;
            }
        }
        while (j <= R)
        {
            v2.push_back(v[j++]);
        }
        while (i <= M)
        {
            v2.push_back(v[i++]);
        }
        for (i = 0; i < v2.size(); i++)
        {
            v[i + L] = v2[i];
        }
        return res;
    }

};
void xiaohe(vector<int>& v)
{
    MergeSort m;
    cout<< m.smallSum(v)<<endl;
}

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对
思路：在Merge过程中，找右边比它小的

class MergeSort2
{
public:
    int niXudui(vector<int>& v)
    {
        if (v.size() < 2)
            return 0;
        int L = 0;
        int R = v.size() - 1;
        return process(v, L, R);
    }
    int process(vector<int>& v, int L, int R)
    {
        if (L == R)
            return 0;
        else
        {
            int M = (L + R) / 2;
            return process(v, L, M) + process(v, M + 1, R) + merge(v, L, M, R);
        }
    }
    int merge(vector<int>& v, int L, int M, int R)
    {
        int count = 0;
        vector<int> v2;
        int i = L;
        int j = M + 1;
        while (i <= M && j <= R)
        {
            if (v[i] > v[j])
            {
                v2.push_back(v[i]);
                 count+=R - j + 1;
                i++;
            }
            else
            {
                v2.push_back(v[j]);
                j++;
            }
        }
        while (j <= R)
        {
            v2.push_back(v[j++]);
        }
        while (i <= M)
        {
            v2.push_back(v[i++]);
        }
        for (i = 0; i < v2.size(); i++)
        {
            v[i + L] = v2[i];
        }
        return count;
    }

};
void nixudui(vector<int>& v)
{
    MergeSort2 m;
    cout << m.niXudui(v) << endl;
}