归并排序之python

想更好的了解归并排序, 需先了解, 将两个有序列表, 组成一个有序列表

有两个列表 l1 = [1, 3, 5, 7]

l2 = [2, 4, 6]

需要将 l1 和 l2 组成一个有序大列表 l = [1, 2, 3, 4, 5, 6, 7]

注意,前提 l1 和 l2 两个列表已经排好序, 是有序列表

 1 def merge(l1, l2):
 2     # 两个列表, 两个初始索引号, 赋值 0
 3     l1_index, l2_index = 0, 0
 4     # 存放结果的新的空列表
 5     result = []
 6     # 循环, 两个索引值都要小于各自列表的长度
 7     while l1_index < len(l1) and l2_index < len(l2):
 8         # 小的数值,则添加到结果列表中, 并把小列表 的索引+1,
 9         # 这样 小列表就指向下一个数据, 和 另一个列表的的数值再次比较
10         if l1[l1_index] < l2[l2_index]:
11             result.append(l1[l1_index])
12             l1_index += 1
13         else:
14             result.append(l2[l2_index])
15             l2_index += 1
16 
17     # l1 和 l2 长度可能相等, 也可能不等
18     # 但是经过while循环后, l1_index 和 l2_index 
19     # 最少有一个,已经到列表的末尾
20     # 所以,如下对两个列表的最后切片取值,
21     # 最少有一个是空列表, 
22     # 直接列表相加, 就省去了判断代码逻辑
23     result += l1[l1_index:]
24     result += l2[l2_index:]
25     return result
26 
27 
28 print(merge([1, 3, 5, 7], [2, 4, 6]))

归并排序的递归算法实现,

直接使用了上面代码的合并 merge 函数

 1 def mergesort(lists):
 2     # 如果列表长度小于等于1
 3     # 说明列表是空列表, 或只有一个元组
 4     # 则不需要排序,直接返回原列表
 5     if len(lists) <= 1:
 6         return lists
 7     # 列表长度除以2
 8     num = int(len(lists) / 2)
 9     # 将列表一分为二,
10     # 再分别对这两个列表进行归并排序
11     left = mergesort(lists[:num])
12     right = mergesort(lists[num:])
13     # 注意,这是递归算法
14     # left 和 right 变成只有一个元素的列表值的时候
15     # 或者, left 和 right 都已是有序列表
16     # 调用merge函数
17     # 可以打印, left 和 right 的值看看,
18     # 感受, left 和 right 的变化
19     # print(left, right)
20     return merge(left, right)
21 
22 
23 print(mergesort([3, 1, 4]))
24 print(mergesort([3, 1, 4, 2]))

归并排序, 将一个列表一分为二, 分别对两个新列表进行归并排序, 然后将这两个排序后的新列表进行合并.

两个被拆分的新列表再次进行归并排序, 直至递归到只有一个元素的情况,

最后, 由最后的两个元素, 开始合并, 逐层向上合并, 实现全部排序

痛点: 是对递归算法的了解