题解 | #数组中的逆序对#

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    func InversePairs ( _ nums: [Int]) -> Int {
// write code here
        var data = nums
        var tmp = [Int].init(repeating: 0, count: nums.count)
        return mergeSort(&data, &tmp, 0, nums.count-1)%1000000007
    }

    func mergeSort(_ nums: inout [Int], _ tmp: inout [Int], _ left: Int, _ right: Int) -> Int {
        //若只有一个元素则不需要继续划分
        if left < right {
            let mid = (left+right)/2
            //递归划分左半区
            let lCount = mergeSort(&nums, &tmp, left, mid)
            //递归划分右半区
            let rCount = mergeSort(&nums, &tmp, mid+1, right)
            //合并已排序部分
            let mCount = mergeArray(&nums, &tmp, left, mid, right)
            return lCount + rCount + mCount
        }
        return 0
    }

    func mergeArray(_ nums: inout [Int], _ tmp: inout [Int], _ left: Int, _ mid: Int, _ right: Int) -> Int {
        //标记左半区第一个未排序的元素
        var l_pos = left
        //标记右半区第一个未排序的元素
        var r_pos = mid + 1
        //临时数组下标
        var pos = left
        //逆序对数量
        var count = 0
        //合并
        while l_pos <= mid && r_pos <= right {
            //若左半区第一个剩余元素更小，放到临时数组，并下标+1
            if nums[l_pos] < nums[r_pos] {
                tmp[pos] = nums[l_pos]
                pos += 1
                l_pos += 1
            } else {
                //右半区第一个剩余元素更小，则左半区l_pos及以后的元素都和它组成逆序对
                tmp[pos] = nums[r_pos]
                pos += 1
                r_pos += 1
                count += mid - l_pos + 1
            }
        }
        //合并左半区剩余的元素
        while l_pos <= mid {
            tmp[pos] = nums[l_pos]
            pos += 1
            l_pos += 1
        }
        //合并右半区剩余的元素
        while r_pos <= right {
            tmp[pos] = nums[r_pos]
            pos += 1
            r_pos += 1
        }
        //将临时数组的元素复制回原来的数组
        var l = left
        while l <= right {
            nums[l] = tmp[l]
            l += 1
        }
        return count
    }
}