归并排序的 3 个优化-1

归并排序的 个优化

归并排序的优化有以下 个角度：

1、如果两个数组，直接拼起来就是有序的，就无须 merge。即当 arr[mid]<=arr[mid+1]
的时候是不用 merge 的；

2、前面我们提到过，“插入排序”在小规模的排序任务上表现出色，这里，我们就可以在小区间里使用插入排序了；

3、我们每次做归并的时候，都 new 了辅助的空间，用完之后就丢弃了。事实上，我们可以全程使用 1 个和待排序数组一样长度的数组作为辅助归并两个排序数组的临时空间，这样就避免了频繁 new 和 delete 数组空间的操作。

下面我们依次说明。

如果数组有序无须归并

例如下面这两个数组，直接把它们接在一起就可以了。

归并排序的 3 个优化-2

Python 代码：

def __merge_sort(nums, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2  # 这是一个陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)

小区间排序使用“插入排序”

我们在介绍“插入排序”的时候，介绍了两种实现方式，我们不妨都实现一下。只不过，我们这里实现的是对原数组的子区间 [left, right] 使用插入排序。

Python 代码1：

def insert_sort_for_merge_1(nums, left, right):
    """
    逐个向前交换的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        for j in range(i, left, -1):  # 这里是 left
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break

Python 代码2：

def insert_sort_for_merge_2(nums, left, right):
    """
    多次赋值的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        temp = nums[i]
        j = i - 1
        # 注意：这里 j 最多到 left
        while j >= left and nums[j] > temp:
            if nums[j] > temp:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = temp

把它们之一应用在递归终止条件：

Python 代码：

def __merge_sort(nums, left, right):
    if right - left <= 15:
        insert_sort_for_merge_2(nums, left, right)
        return
    mid = left + (right - left) // 2  # 这是一个陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)

全局使用一个临时数组用于归并

这里我们直接给出完整的归并排序的代码：

Python 代码：

def __merge_of_two_sorted_array(nums, left, mid, right):
    # 将原数组 [left,right] 区间内的元素复制到辅助数组
    for index in range(left, right + 1):
        nums_for_compare[index] = nums[index]

    # [1,  2, 3,   4,5]
    # left    mid    right
    i = left
    j = mid + 1
    for k in range(left, right + 1):
        if i == mid + 1:
            # i 用完了，就拼命用 j
            nums[k] = nums_for_compare[j]
            j += 1
        elif j > right:
            # j 用完了，就拼命用 i
            nums[k] = nums_for_compare[i]
            i += 1
        elif nums_for_compare[i] < nums_for_compare[j]:
            nums[k] = nums_for_compare[i]
            i += 1
        else:
            assert nums_for_compare[i] >= nums_for_compare[j]
            nums[k] = nums_for_compare[j]
            j += 1


def insert_sort_for_merge_1(nums, left, right):
    """
    逐个向前交换的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        for j in range(i, left, -1):  # 这里是 left
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break


def insert_sort_for_merge_2(nums, left, right):
    """
    多次赋值的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        temp = nums[i]
        j = i - 1
        # 注意：这里 j 最多到 left
        while j >= left and nums[j] > temp:
            if nums[j] > temp:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = temp


def __merge_sort(nums, left, right):
    if right - left <= 15:
        insert_sort_for_merge_2(nums, left, right)
        return
    mid = left + (right - left) // 2  # 这是一个陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)


def merge_sort(nums):
    global nums_for_compare
    nums_for_compare = list(range(len(nums)))
    __merge_sort(nums, 0, len(nums) - 1)

分治思想的应用：计算数组的逆序对

这里给出的例题如果对于初学者来说都偏难，不过其实你只要熟悉归并排序，按照归并排序的套路，是不难写出下面的代码。反正不过我是写不出的，不过我会看别人写的代码，理解之后，自己写出来。如果觉得理解这些代码比较吃力的话，可以暂时跳过，我写出来还是费了很大力气，并且也是调试和一段时间才把代码写正确的。

例1：《剑指 Offer》（第 2 版）第 51 题：计算数组的逆序对

传送门：《剑指 Offer》（第 2 版）第 51 题：计算数组的逆序对。

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例

输入：[1,2,3,4,5,6,0]

输出：6

思路1：首先我们应该想到，使用定义计算逆序数，时间复杂度是：。

class Solution(object):
    def inversePairs(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

这种思路虽然很直接，但编写出错的概率就很低了，在没有在线评测系统的时候，它可以作为一个“正确的”参考答案，用以检验我们自己编写的算法是否正确。

思路2：借助归并排序的分治思想，时间复杂度为 。

分析：例如：前有序数组：，后有序数组：。

做归并的时候，步骤如下：

第 1 步， 先出列， 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 2 步， 出列， 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 3 步， 出列，关键的地方在这里，“前有序数组”中所有剩下的元素 比 都大，构成 个 “逆序对”；

第 4 步， 出列， 比“后有序数组”中所有剩下的元素都小，构成“顺序对”；

第 5 步， 出列，“前有序数组”中所有剩下的元素 比 都大，构成 个“逆序对”；

第 6 步， 出列，“前有序数组”中所有剩下的元素 比 都大，构成 个“逆序对”；

第 7 步， 出列， 比“后有序数组”中所有剩下的元素 都小，构成 个“顺序对”；

第 8 步， 出列，此时“前有序数组”为空。

因此，我们只需要在“前有序数组”非空，且“后有序数组”中有元素出列的时候，即上面的第 3、5、6 步计算“逆序对”就可以了。

Python 代码：

class Solution(object):
    def inversePairs1(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        l = len(nums)
        if l < 2:
            return 0
        temp = [0 for _ in range(l)]
        return self.count_inversion_pairs(nums, 0, l - 1, temp)

    def count_inversion_pairs(self, nums, l, r, temp):
        """
        在数组 nums 的区间 [l,r] 统计逆序对
        :param nums:
        :param l: 待统计数组的左边界，可以取到
        :param r: 待统计数组的右边界，可以取到
        :param temp:
        :return:
        """
        # 极端情况下，就是只有 1 个元素的时候
        if l == r:
            return 0
        mid = l + (r - l) // 2
        left_pairs = self.count_inversion_pairs(nums, l, mid, temp)
        right_pairs = self.count_inversion_pairs(nums, mid + 1, r, temp)

        merge_pairs = 0
        # 代码走到这里的时候，
        # [l, mid] 已经完成了排序并且计算好逆序对
        # [mid + 1, r] 已经完成了排序并且计算好逆序对
        # 如果 nums[mid] <= nums[mid + 1]，此时就不存在逆序对
        # 当 nums[mid] > nums[mid + 1] 的时候，就要继续计算逆序对
        if nums[mid] > nums[mid + 1]:
            # 在归并的过程中计算逆序对
            merge_pairs = self.merge_and_count(nums, l, mid, r, temp)
        # 走到这里有 nums[mid] <= nums[mid + 1] 成立，已经是顺序结构
        return left_pairs + right_pairs + merge_pairs

    def merge_and_count(self, nums, l, mid, r, temp):
        """
        前：[2,3,5,8]，后：[4,6,7,12]
        我们只需要在后面数组元素出列的时候，数一数前面这个数组还剩下多少个数字，
        因为"前"数组和"后"数组都有序，
        因此，"前"数组剩下的元素个数 mid - i + 1 就是与"后"数组元素出列的这个元素构成的逆序对个数
         
        """
        for i in range(l, r + 1):
            temp[i] = nums[i]
        i = l
        j = mid + 1
        res = 0
        for k in range(l, r + 1):
            if i > mid:
                nums[k] = temp[j]
                j += 1
            elif j > r:
                nums[k] = temp[i]
                i += 1
            elif temp[i] <= temp[j]:
                # 不统计逆序对，只做排序
                nums[k] = temp[i]
                i += 1
            else:
                assert temp[i] > temp[j]
                nums[k] = temp[j]
                j += 1
                # 快就快在这里，一次可以数出一个区间的个数的逆序对
                # 例：[7,8,9][4,6,9]，4 与 7 以及 7 前面所有的数都构成逆序对
                res += (mid - i + 1)
        return res

说明：归并两个有序数组的时候，我们要借助额外的辅助空间，为此可以全局使用一个和原始数组等长的辅助数组，否则每一次进入 merge 函数都要 new 新数组，开销很大。

上述解法的缺点是修改了原始数组，排序完成以后，逆序数就计算出来了。为此：1、我们可以引入一个索引数组；2、或者直接拷贝一个原始数组，这样就不用修改原始数组了。

例2：LeetCode 第 315 题：计算右侧小于当前元素的个数

传送门：315. 计算右侧小于当前元素的个数。

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

Python 代码：

class Solution:
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 计算一下左边
        self.__helper(nums, left, mid, temp, indexes, res)
        # 计算一下右边
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组
        # [mid+1,right] 后有序数组

        # 先拷贝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此时前面剩下的数，比后面所有的数都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面两种情况只在其中一种统计就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

说明：这里用到了一个索引数组 indeses，是一个常见的技巧。比如我们交换数组的元素成本很大的时候，可以使用索引数组，交换索引成本很低。这一点，在我们以后介绍索引堆的时候还会用到。

例3：LeetCode 第 53 题：最大子序和

传送门：英文网址：53. Maximum Subarray ，中文网址：53. 最大子序和 。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

分析：这道题其实最先应该想到使用动态规划，使用分治有点“小题大作”，我们不妨把分治解法看做一个例题。

分治的时候，要注意一点，不重不漏。

Python 代码：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        return self.__max_sub_array(nums, 0, n - 1)

    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))

    def __max_cross_array(self, nums, left, mid, right):
        """
        一定包含 nums[mid] 元素的最大连续子数组的和
        思路是看看左边扩散到底，得到一个最大数
        右边扩散到底得到一个最大数
        :param nums:
        :param mid:
        :param right:
        :return:
        """
        ls = 0
        j = mid - 1
        s1 = 0
        while j >= left:
            s1 += nums[j]
            ls = max(ls, s1)
            j -= 1

        rs = 0
        j = mid + 1
        s2 = 0
        while j <= right:
            s2 += nums[j]
            rs = max(rs, s2)
            j += 1

        return ls + nums[mid] + rs


if __name__ == '__main__':
    s = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    result = s.maxSubArray(nums)
    print(result)

在 LeetCode 上面搜索一下，看看还有哪些是分治思想解决的问题。

归并排序的 3 个优化-3

本文源代码

Python：代码文件夹，Java：代码文件夹。

（本节完）