35. 数组中的逆序对 ***这道题挺难的

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

思路
思路一：
暴力解，两个循环，时间复杂度，但是会超出运行时间，导致失败。
思路二：
分治的思想，将数组不断一分为二，直到数组中只有两个元素，统计逆序对个数。然后对相邻的两个子数组进行合并，由于已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行排序，避免在之后的统计过程中重复统计。在合并的时候也要计算组间的逆序对个数。
逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量
整个过程是一个归并排序的算法。
归并排序的性能不受输入数据的影响，时间复杂度始终都是。代价是需要额外的内存空间。

代码实现

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        # 思路一：暴力解，两个循环
        # 运行超时，暴力解不行哦
        length = len(data)
        if(length == 0):
            return 0
        else:
            num = 0
            for i in range(length-1):
                point = data[i]
                for j in range(i,length):
                    if(data[i]>data[j]):
                        num += 1
            return num%1000000007

归并排序的题解：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        num, new_list = self.mergeSort(data)
        return num%1000000007

    def mergeSort(self, data):
        # 逆序对个数
        InversePairsNum = 0
        # 归并过程
        def merge(left,right):
            # 合并时发现的逆序对个数
            InversePairsNum = 0
            result = [] # 保存归并后的结果
            i = j = 0
            while(i<len(left) and j<len(right)):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
                    # 当右边的元素被插入时，证明这个元素比左边的剩下的所有元素都小
                    # 可以组成len(left)-i个逆序对
                    InversePairsNum = InversePairsNum + (len(left)-i)
            result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾,大概率是空的
            return InversePairsNum, result
        # 
        if len(data) <= 1:
            return 0, data
        else:
            mid = len(data)//2 # //是向下取整
            num_left, left = self.mergeSort(data[:mid])
            num_right, right = self.mergeSort(data[mid:])
            num_merge, new_list = merge(left, right)
            InversePairsNum = num_left + num_right + num_merge
            return InversePairsNum, new_list

可以参考归并排序
归并排序 Python 代码实现如下：

def mergeSort(nums):
    # 归并过程
    def merge(left, right):
        result = []  # 保存归并后的结果
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
        return result
    # 递归过程
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

参考文献：
Python实现十大经典排序算法