【算法日积月累】3-归并排序

归并排序 分治 递归

“归并排序”思想虽然很简单，但是对“归并排序”算法的学习，我们可以一窥“分治”和“递归”这两种非常常用的算法思想。

归并排序的思想

归并排序的基本思想是：将两个有序数组归并成一个更大的有序数组。“归并”的过程很简单，请看以下两个有序数组：

有序数组1：$[14,19,22]$。

有序数组2：$[8,16,24]$。

因为数组是有序的，所以每次我们比较每个数组的开头那个元素，谁小，谁拿出来，拿出来的元素的后面的那个元素就成为新的开头元素（我们无须把后面的元素前移一位，只要把定义“开头”的指针后移一位就好了）。所以，我们依次得到 $8,14,16,19,22,24$，这就是“归并”以后的数组。

不难看出，要实现“归并排序”，我们需要与归并之前两个数组元素数目之和的这么多辅助空间。你也很容易想到，只要归并之前，数组是有序的，多来几个有序数组，归并的思路也是一致的：每一次都拿出这些有序数组的第 $1$ 个元素（索引为 $0$）中最小的。

那么代码如何实现呢？这里就要用到“递归”和“分治”的思想。下面是《算法导论》（第 3 版）中关于“归并排序”介绍部分的伪代码。

可以看到：

1、我们要设计一个能在数组 A 的区间 [p,r] 内完成归并排序功能的函数；

2、每一轮找到 p 和 r 的中点 q，把区间 [p,r] 分成两个子区间，对这两个子区间分别递归调用自己；

3、最后“等待”两个递归调用自己的函数都完成以后，再“mege”一下，这一步就是我们上面提到的“归并排序”的思想。

写到这里，可能还是很模糊，这就是“递归”这件事让人有的时候捉摸不透的原因。我们想想递归到底的情况，即两个数组都只有 $1$ 个元素的时候，就容易一些了，这时问题就退化为比较两个数的大小的问题了。下面的代码几乎是“模板”，需要在理解的基础上，记忆和练习。

归并排序的实现（第 1 版）

从上面的伪代码中，我们知道，我们要编写一个支持数组指定区间排序的函数，因为这个函数是内部使用的，我们使用 __ 开头：

def __merge_sort(nums, left, right):
    if left >= right:
        return
    # Python 中整除使用 // 2
    # 下面这行代码在 left 和 right 都很大时，left + right 会溢出
    mid = (left + right) // 2
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    __merge_of_two_sorted_array(nums, left, mid, right)
def merge_sort(nums):
    """
    归并排序的入口函数
    :param nums:
    :return:
    """
    __merge_sort(nums, 0, len(nums) - 1)

说明：1、上面的 __merge_sort 函数就对应了伪代码中的 MERGE-SORT 函数。

2、下面这段代码表示了递归终止条件，即：[left,right] 形成区间时，才调用函数，极端情况下，left==right 时，都不能调用，道理很简单：这个时候，区间只有 $1$ 个元素，都不能拆成两个数组。

if left >= right:
    return

3、mid = (left + right) // 2 这句代码严格意义上说是错误的，正确的写法是：

mid = left + (right - left) // 2

因为如果 left 和 right 都很大的话，left + right 容易越界，我们将在后面的代码中修正它。

下面是合并两个有序数组的代码：

def __merge_of_two_sorted_array(nums, left, mid, right):
    # Python 中切片即复制，复制到一个临时数组中
    nums_for_compare = nums[left:right + 1]
    i = 0
    j = mid - left + 1
    # 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
    # 覆盖原始数组
    for k in range(left, right + 1):
        if i > mid - left:
            # i 用完了，就拼命用 j
            nums[k] = nums_for_compare[j]
            j += 1
        elif j > right - left:
            # 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 __merge_of_two_sorted_array(nums, left, mid, right):
    # Python 中切片即复制，复制到一个临时数组中
    nums_for_compare = nums[left:right + 1]
    i = 0
    j = mid - left + 1
    # 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
    # 覆盖原始数组
    for k in range(left, right + 1):
        if i > mid - left:
            # i 用完了，就拼命用 j
            nums[k] = nums_for_compare[j]
            j += 1
        elif j > right - left:
            # 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 __merge_sort(nums, left, right):
    if left >= right:
        return
    # 这是一个陷阱，如果 left 和 right 都很大的话，left + right 容易越界
    # Python 中整除使用 // 2
    mid = left + (right - left) // 2
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    __merge_of_two_sorted_array(nums, left, mid, right)
def merge_sort(nums):
    """
    归并排序的入口函数
    :param nums:
    :return:
    """
    __merge_sort(nums, 0, len(nums) - 1)

这就是我们实现的第 1 版归并排序。

时间复杂度与空间复杂度

时间复杂度：$O(n\log n)$

这是我们接触的第 1 个 $O(n\log n)$ 级别的排序算法，它比前两个 $O(n^2)$ 级别快的原因就是，每次我们都一分为二地处理数组，不用在一个很长的数组里进行排序。但它需要辅助的空间来执行“归并”操作，算是一种以“空间”换“时间”的策略吧。

为什么是 $\log n$ 呢？因为“归并”的操作呈树形结构。

空间复杂度：$O(n)$

分析：我们在合并两个有序数组的时候，使用了与两个数组长度之和这么多空间的辅助数组，所以“归并排序”的空间复杂度是 $O(n)​$。

这一节的内容就暂时介绍这么多，开始我们慢一点。下一节，我们介绍归并排序的优化。

练习

练习1：LeetCode 第 88 题：合并两个有序数组

要求：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

解法1：你当然可以按照我们这一节介绍的合并两个有序数组的方法来完成，因为最后是把 nums1 返回回去，因此，我们要先把 nums1 中的元素拷贝出来，然后再写回 nums1。

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        nums3 = nums1[:]
        i = 0
        j = 0
        for k in range(m + n):
            if i == m:
                nums1[k] = nums2[j]
                j += 1
            elif j == n:
                nums1[k] = nums3[i]
                i += 1
            elif nums3[i] < nums2[j]:
                nums1[k] = nums3[i]
                i += 1
            else:
                nums1[k] = nums2[j]
                j += 1
if __name__ == '__main__':
    nums1 = [1, 2, 3, 4, 5, 6, 7, 20, 30, 40, 50]
    nums2 = [8, 9, 10, 11, 12, 60, 70, 80]
    m = len(nums1)
    n = len(nums2)
    nums1.extend([None] * n)
    s = Solution()
    s.merge(nums1, m, nums2, n)
    print(nums1)

解法2：考虑到这道问题的特殊性，即 nums1 有足够的空间，因此，我们可以从后向前归并，每次从两个数组的末尾选出最大的元素放在 nums1 的末尾，而不用辅助数组空间。

你可能会担心，nums1 之前有效的元素会不会被覆盖掉，在这题中，这种情况是不可能出现的。在实现的时候，还是要特别注意一些边界条件。

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i = m - 1
        j = n - 1
        for k in range(m + n - 1, -1, -1):
            if i == -1: 
                nums1[k] = nums2[j]
                j -= 1
            elif j == -1:
                nums1[k] = nums1[i]
                i -= 1
            elif nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1

（完）