没流泪，不代表没眼泪；无所谓，不代表无所累。这个世界本就邋遢，所以没有什么可怕。每个人都有无法发泄的苦涩，都有无力排解的抑郁，而生活在那里的我们，哪一个不是拼尽全力，甚至不择手段地活着。
假设有2个有序列表l1、l2，如何效率比较高的将2个list合并并保持有序状态，这里默认排序是正序。
思路是比较简单的，无非是依次比较l1和l2头部第一个元素，将比较小的放在一个新的列表中，以此类推，直到所有的元素都被放到新的列表中。
考虑2个列表l1 = [2], l2 = [1]，如何将他们合并呢？(注意：下面实现会改变l1和l2本来的值)
def signle_merge_sort(l1, l2):
tmp = []
if l1[0] < l2[0]:
tmp.append(l1[0])
tmp.extend(l2)
del l2[0]
else:
tmp.append(l2[0])
tmp.extend(l1)
del l1[0]
return tmp
这真的只能处理一个元素的情形，还不能解决问题，不过好歹我们有一个大概的思路了。如果有列表中2个元素，上面的方法就不行了。我们需要解决边界判断问题，即当l1或者l2有一个为空的时，将剩下的一个list加到排序结果的尾部。然后确保函数每次调用只处理一个元素，通过递归来解决问题。
def recursion_merge_sort1(l1, l2):
tmp = []
if len(l1) == 0:
tmp.extend(l2)
return tmp
elif len(l2) == 0:
tmp.extend(l1)
return tmp
else:
if l1[0] < l2[0]:
tmp.append(l1[0])
del l1[0]
else:
tmp.append(l2[0])
del l2[0]
tmp += recursion_merge_sort1(l1, l2)
return tmp
上面的程序有2个问题：if判断太多；每次都要初始化tmp，对内存使用似乎不太友好。考虑到程序在l1或者l2有一个为空的时候就终止，可以稍微改写一下：
def _recursion_merge_sort2(l1, l2, tmp):
if len(l1) == 0 or len(l2) == 0:
tmp.extend(l1)
tmp.extend(l2)
return tmp
else:
if l1[0] < l2[0]:
tmp.append(l1[0])
del l1[0]
else:
tmp.append(l2[0])
del l2[0]
return _recursion_merge_sort2(l1, l2, tmp)def recursion_merge_sort2(l1, l2):
return _recursion_merge_sort2(l1, l2, [])
但是对于Python而言，即使是尾递归，效率也不是那么高，为了避免爆栈，通常还是会用循环来做，再稍微改写一下:
def loop_merge_sort(l1, l2):
tmp = []
while len(l1) > 0 and len(l2) > 0:
if l1[0] < l2[0]:
tmp.append(l1[0])
del l1[0]
else:
tmp.append(l2[0])
del l2[0]
tmp.extend(l1)
tmp.extend(l2)
return tmp
今天栽了个坑，好好反省，就是这样。
到此这篇关于Python对两个有序列表进行合并和排序的例子就介绍到这了。为了以后能随时偷懒，现在就得时刻努力。更多相关Python对两个有序列表进行合并和排序的例子内容请查看相关栏目，小编编辑不易，再次感谢大家的支持！
