归并排序法：是采用分治法的一个非常典型的应用。
分治法:
分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
#归并排序法
#1、合并的过程函数
left 开始索引下标；m数组中间值下标；right结束索引下标
def merge(arr,left,m,right):
n1=m-left+1 #前子数组的长度
n2=right-m #后子数组的长度
创建临时数组
L=[0]n1
R=[0]n2
拷贝数据到临时数组
for i in range(0,n1): #把前子数组的元素拷贝到左边的临时数组
L[i]=arr[left+i]
for j in range(0,n2): #把后子数组的元素拷贝到右边的临时数组
R[j]=arr[m+1+j]
归并临时数组到 arr[1..r]
把左右临时数组的元素，按大小合并到原数组中
i=0 #初始化第一个子数组的索引
j=0 #初始化第二个子数组的索引
k=left #初始归并子数组的索引
while i < n1 and j
k +=1
拷贝 L[] 剩下的保留元素
如果右边的数字元素都并入完了，左边数组还有元素，则不需要再进行比较，集中并入
while i
拷贝 R[]剩下 的保留元素
如果左边的数字元素都并入完了，右边数组还有元素，则不需要再进行比较，集中并入
while j
#2、分 的过程
先分：一直分到单个元素后，从单个元素再合并的操作
def mergeSort(arr,left,right):
if left >= right:
return
m=int((left+right)/2)
mergeSort(arr,left,m) #递归对数列的前半部分进行分开
mergeSort(arr,m+1,right) #递归对数列的后半部分进行分开
merge(arr,left,m,right) #从分开后的单个元素开始进行合并
测试
arr=[8,4,7,5,3,1,6,2]
n=len(arr)
mergeSort(arr,0,n-1)
print(“排序后的数值”)
for i in range(n):
print(“%d” %arr[i])
Original: https://www.cnblogs.com/xiangers/p/15458333.html
Author: xiangers
Title: Python 归并排序法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/510998/
转载文章受原作者版权保护。转载请注明原作者出处！