@liweiwei1419
2019-01-20T01:42:08.000000Z
字数 4395
阅读 1143
归并排序
分治
递归
“归并排序”思想虽然很简单,但是对“归并排序”算法的学习,我们可以一窥“分治”和“递归”这两种非常常用的算法思想。
归并排序的基本思想是:将两个有序数组归并成一个更大的有序数组。“归并”的过程很简单,请看以下两个有序数组:
有序数组1:。
有序数组2:。
因为数组是有序的,所以每次我们比较每个数组的开头那个元素,谁小,谁拿出来,拿出来的元素的后面的那个元素就成为新的开头元素(我们无须把后面的元素前移一位,只要把定义“开头”的指针后移一位就好了)。所以,我们依次得到 ,这就是“归并”以后的数组。
不难看出,要实现“归并排序”,我们需要与归并之前两个数组元素数目之和的这么多辅助空间。你也很容易想到,只要归并之前,数组是有序的,多来几个有序数组,归并的思路也是一致的:每一次都拿出这些有序数组的第 个元素(索引为 )中最小的。
那么代码如何实现呢?这里就要用到“递归”和“分治”的思想。下面是《算法导论》(第 3 版)中关于“归并排序”介绍部分的伪代码。
可以看到:
1、我们要设计一个能在数组 A
的区间 [p,r]
内完成归并排序功能的函数;
2、每一轮找到 p
和 r
的中点 q
,把区间 [p,r]
分成两个子区间,对这两个子区间分别递归调用自己;
3、最后“等待”两个递归调用自己的函数都完成以后,再“mege”一下,这一步就是我们上面提到的“归并排序”的思想。
写到这里,可能还是很模糊,这就是“递归”这件事让人有的时候捉摸不透的原因。我们想想递归到底的情况,即两个数组都只有 个元素的时候,就容易一些了,这时问题就退化为比较两个数的大小的问题了。下面的代码几乎是“模板”,需要在理解的基础上,记忆和练习。
从上面的伪代码中,我们知道,我们要编写一个支持数组指定区间排序的函数,因为这个函数是内部使用的,我们使用 __
开头:
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
时,都不能调用,道理很简单:这个时候,区间只有 个元素,都不能拆成两个数组。
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 版归并排序。
这是我们接触的第 1 个 级别的排序算法,它比前两个 级别快的原因就是,每次我们都一分为二地处理数组,不用在一个很长的数组里进行排序。但它需要辅助的空间来执行“归并”操作,算是一种以“空间”换“时间”的策略吧。
为什么是 呢?因为“归并”的操作呈树形结构。
分析:我们在合并两个有序数组的时候,使用了与两个数组长度之和这么多空间的辅助数组,所以“归并排序”的空间复杂度是 。
这一节的内容就暂时介绍这么多,开始我们慢一点。下一节,我们介绍归并排序的优化。
要求:给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
示例:
输入:
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
(完)