基于Python3的数据结构与算法 - 07 归并排序

一、归并

引入

��设现在的列表分两段有序，如何将其合并成为一个有序列表。

这种操作成为一次归并。

归并的思路

1. 分别对两个列表进行遍历，比较两个列表中的最小值，将更小的取出来。
2. 取出后一次进行上操作，直到其中一个列表中的元素被取完。
3. 再直接将列一个列表中的剩下元素全部取出。

实现代码如下：

def merge(li, low, mid, high):    # 两个列表合并一块，最左边为low，最右边为high，第一个列表的最后一个元素下标为mid    # 则列表被分为两部分，一个为low - mid，另一个为mid+1 - high    # 最开始定义两个箭头 + 一个存放返回的空列表    i = low    j = mid +1    ltmp = []    while i