编辑代码

"""归并排序"""
def mergeSort(nums: list):
    if len(nums) == 1:
        return nums
    nums1 = mergeSort(nums[0: (len(nums) // 2)])
    nums2 = mergeSort(nums[(len(nums) // 2): len(nums)])
    return merge(nums1, nums2)


def merge(nums1: list, nums2: list):
    i = 0
    j = 0
    temp = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            temp.append(nums1[i])
            i += 1
        else:
            temp.append(nums2[j])
            j += 1

    temp += nums1[i: len(nums1)] if i < j else nums2[j: len(nums2)]
    return temp
"""归并排序"""


"""寻找逆序对"""
def findReverseOrderPairs(nums: list, result: list):
    if len(nums) <= 1:
        return nums
    nums1 = findReverseOrderPairs(nums[0: len(nums) // 2], result)
    nums2 = findReverseOrderPairs(nums[len(nums) // 2: len(nums)], result)
    temp = find(nums1, nums2)
    if len(temp) > 0:
        result += temp
    return merge(nums1, nums2) #调用归并排序的归并


def find(nums1, nums2):
    j = 0
    temp = []
    while j < len(nums2):
        for each in nums1:
            if nums2[j] < each:
                temp.append([each, nums2[j]])
            else:
                break
        j += 1
    return temp
"""寻找逆序对"""


if __name__ == '__main__':
    nums = [5, 6, 8, 1, 4, 3, 8, 7]
    print(mergeSort(nums))
    arr = []
    findReverseOrderPairs(nums, arr)
    print(arr)