【剑指offer】数组中的逆序对（python）

思路：先把数组分割成子数组，先统计出子数组内部的逆序对数目，然后统计出两个相邻子数组之间的逆序对数目。统计过程中，还需要对数组进行排序，以免重复统计。
两个指针分别指向两个子数组的末尾，如果第一个子数组的数字大于第二个数组的数字，构成逆序对，并且逆序对数目等于第二个子数组中剩余数字个数，每一次比较都把较大数字从后往前复制到辅助数组中。

# -*- coding:utf-8 -*-
class Solution:
    tmp = []
    cnt = 0
    def InversePairs(self, data):
        # write code here
        self.tmp = [-1 for i in range(len(data))]
        self.mergeSort(data, 0 , len(data)-1)
        return int(self.cnt % 1000000007)
    def mergeSort(self, data, l, h):
        if h - l  < 1: return
        m = (h+l)//2
        self.mergeSort(data, l, m)
        self.mergeSort(data, m+1, h)
        self.merge(data, l, m, h)
    def merge(self, data, l, m, h):
        i = l
        j = m + 1
        k = l
        while i <= m or j <= h:
            if i > m:
                self.tmp[k] = data[j]
                j+=1
            elif j > h:
                self.tmp[k] = data[i]
                i+=1
            elif data[i] <= data[j]:
                self.tmp[k] = data[i]
                i+=1
            else:
                self.tmp[k] = data[j]
                j += 1
                self.cnt += (m - i + 1) # nums[i]>nums[j]，说明nums[i...m]都大于nums[i]
            k += 1
        for m in range(l, h+1):
            data[m] = self.tmp[m]

归并排序的代码，关键在于处理左边+处理右边+归并，归并中关键在于辅助数组，使用temp中的元素覆盖nums中元素。

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        start = 0
        end = length - 1
        return self.sort(nums, start, end)
    def sort(self, nums, low, high):
        mid = (low + high) // 2
        if low < high:
            # 处理左边
            self.sort(nums, low, mid)
            # 处理右边
            self.sort(nums, mid+1, high)
            # 左右归并
            self.merge(nums, low, mid, high);
        return nums
    def merge(self,nums, low, mid, high):
        tmp = [-1 for i in range(high - low + 1)]
        i = low
        j = mid+1
        k = 0
        # 找出较小值元素放入temp数组中
        while i<=mid and j<=high:
            if nums[i] <= nums[j]:
                tmp[k]=nums[i]
                k+=1
                i+=1
            else:
                tmp[k]=nums[j]
                k+=1
                j+=1
        # 处理较长部分
        while i<=mid:
            tmp[k] = nums[i]
            k+=1
            i+=1
        while j<=high:
            tmp[k] = nums[j]
            k+=1
            j+=1
        # 使用temp中的元素覆盖nums中元素
        for k2 in range(len(tmp)):
            nums[k2+low] = tmp[k2]