python实现【归并排序】(MergeSort)
算法原理及介绍
归并排序的核心原理是采用分治法（Divide and Conquer），递归调用；将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。然后将两个有序表合并成一个有序表，最终完成所有元素的排序。
算法过程描述
具体算法过程描述如下：
- 把长度为
n的输入序列分成两个长度为n/2的子序列； - 对这两个子序列分别采用归并排序（递归调用）；
- 将两个排序好的子序列合并成一个最终的排序序列。
算法排序图解如下
在这里插入图片描述
python实现代码
def merge(left, right):
# 合并两个有序列表
res = []
while len(left) > 0 and len(right) > 0:
if left[0] < right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
if left:
res.extend(left)
if right:
res.extend(right)
return res
def mergeSort(arr):
# 归并函数
n = len(arr)
if n < 2:
return arr
middle = n // 2
left = arr[:middle] # 取序列左边部分
right = arr[middle:]# 取序列右边部分
# 对左边部分序列递归调用归并函数
left_sort = mergeSort(left)
# 对右边部分序列递归调用归并函数
right_sort = mergeSort(right)
#
return merge(left_sort, right_sort)
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法：
