[关闭]
@liweiwei1419 2019-01-19T17:42:08.000000Z 字数 4395 阅读 1098

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

归并排序 分治 递归



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

归并排序的思想

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

有序数组1:

有序数组2:

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

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

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

image-20190111215502126

可以看到:

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

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

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

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

归并排序的实现(第 1 版)

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

  1. def __merge_sort(nums, left, right):
  2. if left >= right:
  3. return
  4. # Python 中整除使用 // 2
  5. # 下面这行代码在 left 和 right 都很大时,left + right 会溢出
  6. mid = (left + right) // 2
  7. __merge_sort(nums, left, mid)
  8. __merge_sort(nums, mid + 1, right)
  9. __merge_of_two_sorted_array(nums, left, mid, right)
  10. def merge_sort(nums):
  11. """
  12. 归并排序的入口函数
  13. :param nums:
  14. :return:
  15. """
  16. __merge_sort(nums, 0, len(nums) - 1)

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

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

  1. if left >= right:
  2. return

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

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

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

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

  1. def __merge_of_two_sorted_array(nums, left, mid, right):
  2. # Python 中切片即复制,复制到一个临时数组中
  3. nums_for_compare = nums[left:right + 1]
  4. i = 0
  5. j = mid - left + 1
  6. # 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
  7. # 覆盖原始数组
  8. for k in range(left, right + 1):
  9. if i > mid - left:
  10. # i 用完了,就拼命用 j
  11. nums[k] = nums_for_compare[j]
  12. j += 1
  13. elif j > right - left:
  14. # j 用完了,就拼命用 i
  15. nums[k] = nums_for_compare[i]
  16. i += 1
  17. elif nums_for_compare[i] < nums_for_compare[j]:
  18. nums[k] = nums_for_compare[i]
  19. i += 1
  20. else:
  21. assert nums_for_compare[i] >= nums_for_compare[j]
  22. nums[k] = nums_for_compare[j]
  23. j += 1

完整归并排序的代码如下:

  1. def __merge_of_two_sorted_array(nums, left, mid, right):
  2. # Python 中切片即复制,复制到一个临时数组中
  3. nums_for_compare = nums[left:right + 1]
  4. i = 0
  5. j = mid - left + 1
  6. # 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
  7. # 覆盖原始数组
  8. for k in range(left, right + 1):
  9. if i > mid - left:
  10. # i 用完了,就拼命用 j
  11. nums[k] = nums_for_compare[j]
  12. j += 1
  13. elif j > right - left:
  14. # j 用完了,就拼命用 i
  15. nums[k] = nums_for_compare[i]
  16. i += 1
  17. elif nums_for_compare[i] < nums_for_compare[j]:
  18. nums[k] = nums_for_compare[i]
  19. i += 1
  20. else:
  21. assert nums_for_compare[i] >= nums_for_compare[j]
  22. nums[k] = nums_for_compare[j]
  23. j += 1
  24. def __merge_sort(nums, left, right):
  25. if left >= right:
  26. return
  27. # 这是一个陷阱,如果 left 和 right 都很大的话,left + right 容易越界
  28. # Python 中整除使用 // 2
  29. mid = left + (right - left) // 2
  30. __merge_sort(nums, left, mid)
  31. __merge_sort(nums, mid + 1, right)
  32. __merge_of_two_sorted_array(nums, left, mid, right)
  33. def merge_sort(nums):
  34. """
  35. 归并排序的入口函数
  36. :param nums:
  37. :return:
  38. """
  39. __merge_sort(nums, 0, len(nums) - 1)

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

时间复杂度与空间复杂度

时间复杂度:

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

为什么是 呢?因为“归并”的操作呈树形结构。

空间复杂度:

分析:我们在合并两个有序数组的时候,使用了与两个数组长度之和这么多空间的辅助数组,所以“归并排序”的空间复杂度是

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

练习

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

要求:给定两个有序整数数组 nums1nums2,将 nums2 合并到 nums1使得 num1 成为一个有序数组。

说明:

示例:

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

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

  1. class Solution:
  2. def merge(self, nums1, m, nums2, n):
  3. """
  4. :type nums1: List[int]
  5. :type m: int
  6. :type nums2: List[int]
  7. :type n: int
  8. :rtype: void Do not return anything, modify nums1 in-place instead.
  9. """
  10. nums3 = nums1[:]
  11. i = 0
  12. j = 0
  13. for k in range(m + n):
  14. if i == m:
  15. nums1[k] = nums2[j]
  16. j += 1
  17. elif j == n:
  18. nums1[k] = nums3[i]
  19. i += 1
  20. elif nums3[i] < nums2[j]:
  21. nums1[k] = nums3[i]
  22. i += 1
  23. else:
  24. nums1[k] = nums2[j]
  25. j += 1
  26. if __name__ == '__main__':
  27. nums1 = [1, 2, 3, 4, 5, 6, 7, 20, 30, 40, 50]
  28. nums2 = [8, 9, 10, 11, 12, 60, 70, 80]
  29. m = len(nums1)
  30. n = len(nums2)
  31. nums1.extend([None] * n)
  32. s = Solution()
  33. s.merge(nums1, m, nums2, n)
  34. print(nums1)

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

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

  1. class Solution:
  2. def merge(self, nums1, m, nums2, n):
  3. """
  4. :type nums1: List[int]
  5. :type m: int
  6. :type nums2: List[int]
  7. :type n: int
  8. :rtype: void Do not return anything, modify nums1 in-place instead.
  9. """
  10. i = m - 1
  11. j = n - 1
  12. for k in range(m + n - 1, -1, -1):
  13. if i == -1:
  14. nums1[k] = nums2[j]
  15. j -= 1
  16. elif j == -1:
  17. nums1[k] = nums1[i]
  18. i -= 1
  19. elif nums1[i] > nums2[j]:
  20. nums1[k] = nums1[i]
  21. i -= 1
  22. else:
  23. nums1[k] = nums2[j]
  24. j -= 1

(完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注