加载中…Python对两个有序列表进行合并和排序的例子
(2018-05-04 10:10:27)
标签：
python机器学习数据分析数据分析师培训数据挖掘 |
这篇文章主要介绍了Python对两个有序列表进行合并和排序的例子,最终代码经过不断优化,小编非常满意,需要的朋友可以参考下
假设有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
def signle_merge_sort(l1, l2):
这真的只能处理一个元素的情形，还不能解决问题，不过好歹我们有一个大概的思路了。如果有列表中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
def recursion_merge_sort1(l1, l2):
上面的程序有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, tmp):
def 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
def loop_merge_sort(l1, l2):
今天栽了个坑，好好反省，就是这样。
喜欢
0
赠金笔