面试题51：数组中的逆序对（slow）

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

思路：
这道题可以在归并排序的基础上作答，具体如下：

51 数组中的逆序对(归并排序法).png

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if not data or len(data)<=0:
            return 0
        #一般情况
        #初始化参数
        length = len(data)
        copy = [0]*length
        #辅助元素赋值
        for i in range(length):
            copy[i] = data[i]
        result = self.Core(data,copy,0,length-1)
        return result % 1000000007
    #归并排序核心函数
    def Core(self, data, copy, start, end):
        #递归结束条件
        if start == end:
            copy[start] = data[start]
            return 0
        leng = (end - start) // 2
        #递归进行排序
        left = self.Core(copy,data,start,start + leng)  #改变copy的值
        right = self.Core(copy,data,start+leng+1,end)

        count = 0
        i = leng + start
        j = end
        CopyIndex = end
        #进行归并
        while(i>=start and j>=start+leng+1):
            if data[i]> data[j]:
                copy[CopyIndex] = data[i]
                CopyIndex-=1
                i-=1
                count +=j-leng-start   #因为按顺序，所以第二个数组前面的都会和这个数字成为逆序对
            else:
                copy[CopyIndex] =data[j]
                CopyIndex-=1
                j-=1
        while i>= start:
            copy[CopyIndex] = data[i]
            CopyIndex-=1
            i-=1
        while j>=leng+1+start:
            copy[CopyIndex] = data[j]
            CopyIndex-=1
            j-=1
        return left + count + right

提交结果：(慢)

image.png