写在前面

题目：剑指offer-数组中的逆序对
考点： 归并排序。

知识点

  • 归并排序

要求

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007
题目保证输入的数组中没有的相同的数字

暴力解

class Solution {
public:
    int InversePairs(vector<int> data) {
        int res = 0,n = data.size();
        for(int i=0;i<n;++i) {
            for(int j=i+1;j<n;++j) {
                if(data[i]>data[j]) {
                    ++res;
                    res%=1000000007;
                }
            }
        }
        return res%1000000007;
    }
};

问题：时间复杂度o(n*n)。时间复杂度太高超时。

进阶解

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()==0) return 0;
        int res = 0,n = data.size();
        vector<int> v(data);
        res += helper(data,v,0,n-1);
        return res;
    }

    int helper(vector<int>& data,vector<int>& v,int l,int r) {
        if(r-l==0) return 0;
        int count = 0,mid = l +(r-l)/2;
        int left = helper(v,data,l,mid);
        int right = helper(v,data,mid+1,r);
        int i = mid, j = r, k = r;
        while(i>=l&&j>=mid+1) {
            if(data[i]>data[j]) {
                count += j - mid;
                v[k--] = data[i--];
            }
            else {
                v[k--] = data[j--];
            }
        }
        for(;i>=l;i--) {
            v[k--] = data[i];
        }
        for(;j>=mid+1;j--) {
            v[k--] = data[j];
        }
        return count + left + right;
    }
};

分析

采用归并排序的思想：两两一组先排序比较内部的逆序个数。再将排好序的两组进行比较计算组间逆序数。递归进行。
算法复杂度为o(nlogn)。

核心分析

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序分为两步，第一步是将待排序的数分成两部分，将两部分分别有序，再将两个有序的部分合并。

将两个有序数列合并的时间复杂度为o(n)。归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

单链表的归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* mid = findmid(head);
        ListNode* head1 = sortList(head);//递归二分链表
        ListNode* head2 = sortList(mid);
        return merge(head1,head2);
    }
    ListNode* findmid(ListNode* head) {
        ListNode* fast = head,*slow = head,*pre = head;
        while(fast) {
            pre = slow;
            slow = slow->next;
            fast = fast->next?fast->next->next:nullptr;
        }
        pre->next = nullptr;//需要截断链表彻底一分为2
        return slow;
    }
    ListNode* merge(ListNode* head1,ListNode* head2) {
        ListNode* cur1 = head1,*cur2 = head2,* newhead = new ListNode(0),*cur = newhead;
        while(cur1&&cur2) {
            if(cur1->val<=cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            }
            else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        cur->next = cur1?cur1:cur2;
        return newhead->next;
    }
};

数组的归并排序

#include "MergeSort.h"
#include <iostream>

void MergeSort::solution(std::vector<int>& nums) {
    if (nums.size() < 2) return;
    nums = mergesort(0, nums.size() - 1, nums);
    return;
}

vector<int> MergeSort::mergesort(int l, int r, vector<int>& nums) {
    vector<int> temp;
    if (l == r) {
        temp.push_back(nums[l]);
        return temp;
    }
    if (l + 1 == r) {
        if (nums[l] < nums[r]) {
            temp.push_back(nums[l]);
            temp.push_back(nums[r]);
            return temp;
        }
        else {
            temp.push_back(nums[r]);
            temp.push_back(nums[l]);
            return temp;
        }
    }
    int mid = l + (r - l) / 2;
    vector<int> v1 = mergesort(l, mid - 1, nums);
    vector<int> v2 = mergesort(mid, r,nums);
    temp =  merge(v1, v2);
    return temp;
}

vector<int> MergeSort::merge(vector<int>& v1, vector<int>& v2) {
    if (!v1.size()) return v2;
    else if (!v2.size()) return v1;
    vector<int>res;
    int n = v1.size(), m = v2.size(), i = 0, j = 0;
    while (i < n && j < m) {
        if (v1[i] < v2[j]) {
            res.push_back(v1[i]);
            ++i;
        }
        else {
            res.push_back(v2[j]);
            ++j;
        }
    }
    for (; i < n; ++i) {
        res.push_back(v1[i]);
    }
    for (; j < m; ++j) {
        res.push_back(v2[j]);
    }
    return res;
}

总结

快速排序更适用于数组，归并排序更适用于链表。
因为对于归并排序而言对于数组需要开辟o(n)的额外空间存储排完序的数组对于链表而言并不需要只需要将对应顺序的结点连接起来即可没有额外的空间开销。所以同样是nlogn的算法快排更适用于数组。