「@Author：Runsen」
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」
❞
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
分治算法
分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题 直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。（百度百科）
利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。
分治算法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
分治法所能解决的问题一般具有以下几个特征：
原问题于分解成的小问题具有相同的模式，原问题分解成的小问题可以独立求解，子问题之间没有相关性。
具有分解终止条件，当问题足够小时，可以之间求解，分解出的子问题的解可以合并为该问题的解
基本步骤
- 分解，将要解决的问题划分成若干规模较小的同类问题；
- 求解，当子问题划分得足够小时，用较简单的方法解决；
- 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
具体伪代码如下：
if (问题不可分):
返回解
else:
从原问题中划出含一半运算对象的子问题1；
递归调用分治法过程，求出解1；
从原问题中划出含另一半运算对象的子问题2；
递归调用分治法过程，求出解2；
将解1、解2组合成整个问题的解；
复制
归并排序
分治算法问题求解，一个是二分搜索，一个就是归并排序。
归并排序其实要做两件事：
「拆分」：核心问题是确定拆分位置即可，我们利用左右元素索引之和除2即可，也就是：
mid = (left + right)/2
，指导拆分到子序列仅仅存在一个元素的基本情形。
「合并」：merge 是归并排序的核心，将两个已排序子序列合并为一个排序序列的过程。当子序列中仅存在一个元素时，可视为子序列已经排序，因此我们的合并是从两个单一元素子序列开始的。
当子序列存在多个元素时，我们需要逐个得到当前最小元素，进而完成整体排序，过程中我们需要一个临时区来存储已排序的部分。
最后将两个区间合并为一个有序的区间，你会怎么思考呢？
这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/21
'''
def merge(left, right): # 合并两个有序数组
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
def merge_sort(nums):
if len(nums) <= 1:
return nums
num = len(nums) >> 1 #位运算取中间
left = merge_sort(nums[:num])
right = merge_sort(nums[num:])
return merge(left, right)
if __name__ == '__main__':
nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(merge_sort(nums))
[17, 20, 26, 31, 44, 54, 55, 77, 93]
复制
归并排序的运行时间最差、最好和平均都是
O(NlogN)
，但是归并排序并没有像快排那样，应用广泛，这是为什么呢？因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。它需要额外的存储空间，空间复杂度为
O(N)
。
「这世上没有天才，你若对得起时间，时间便对得起你。关注我们，每天进步一点点，利用碎片化时间学习。」
❝本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。
❞
Reference
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -