学习日历day02 分治法-归并排序（递归版）

归并排序

快速排序类似于二叉树前序遍历（根节点、左子节点、右子节点）

归并排序类似于二叉树后序遍历（左子节点、右子节点、根节点）

归并排序的递归实现

归并排序：持续分割区间，直到剩下最后一个节点，在归并排序的过程中，数组的分割可以看作是在构建一棵二叉树。具体来说，每次分割都将当前数组分为两半，这对应于二叉树中节点分裂成左右两个子节点的过程。当数组不能再分时，就相当于到达了二叉树的叶子节点。

归并排序与二叉树后序遍历之间的相似性体现在合并阶段。在二叉树的后序遍历中，我们首先访问左子树，然后访问右子树，最后访问根节点。而在归并排序的合并阶段，也是先处理（或说排序）左边的部分，再处理右边的部分，最后合并这两个已经排序好的部分。这个过程正好符合后序遍历的顺序：先解决子问题（左子树、右子树），再解决父问题（根节点）。

简而言之，归并排序的分解过程像是从根到叶子节点的前序遍历，而其合并过程则类似于从叶子节点回到根节点的后序遍历。这种结构上的相似性使得人们常常把归并排序与二叉树的后序遍历联系起来。不过需要注意的是，这只是从操作顺序上的一种类比，并不是严格意义上的相同，因为归并排序涉及的具体

# 归并排序递归版
def merge_sort(arr):
    if len(arr)<=1:
        return arr
    mid=len(arr)//2
    llist=arr[:mid]
    rlist=arr[mid:]
    leftsorted=merge_sort(llist)#程序执行完毕才会返回，所以此时的leftsorted一定是排序好的左边数组
    rightsorted=merge_sort(rlist)
    return merge(leftsorted,rightsorted)

def merge(l,r):
    i=0
    j=0
    temp=[]
    while i<len(l) and j<len(r):
        if l[i]<r[j]:
            temp.append(l[i])
            i+=1
        else:
            temp.append(r[j])
            j+=1
    while i<len(l):
        temp.append(l[i])
        i+=1
    while j<len(r):
        temp.append(r[j])
        j+=1
    return temp

a=[33,43,2,5,24,3,73,86,45,23,97,100]
arr1=merge_sort(a)
print(arr1)

操作（如比较和交换元素）与二叉树遍历的操作完全不同。