Python对两个有序列表进行合并和排序的例子
更新时间：2014年06月13日 10:28:56 投稿：junjie
这篇文章主要介绍了Python对两个有序列表进行合并和排序的例子,最终代码经过不断优化,小编非常满意,需要的朋友可以参考下
（福利推荐：【腾讯云】服务器最新限时优惠活动，云服务器1核2G仅99元/年、2核4G仅768元/3年，立即抢购>>>：9i0i.cn/qcloud）
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
假设有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 Pillow图像处理方法汇总,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2019-10-10
这篇文章主要介绍了python实现mysql的单引号字符串过滤方法,以一个较为详细的实例形式分析了Python针对MySQL的操作及字符串过滤的技巧,具有一定参考借鉴价值,需要的朋友可以参考下2015-11-11
本文主要介绍了如何利用Python的ffmpy库实现提取视频中的音频，从而帮助大家更好的理解和学习使用python，感兴趣的朋友可以了解下2021-11-11
这篇文章主要介绍了Python的装饰器详情，主要介绍装饰器定以、调用方式等相关内容，需要的小伙伴可以参考一下，希望对你的学习有所帮助2022-03-03
这篇文章主要介绍了Python变量教程字节对象与字符串，字节对象是字节序列，而字符串是字符序列，字节对象在内部是机器可读的形式，字符串只是人类可读的形式2022-08-08
一文带你了解Python中的type,isinstance和issubclass
这篇文章主要为大家详细介绍了Python中的type、isinstance和issubclass的使用，文中的示例代码讲解详细，感兴趣的小伙伴可以了解一下2023-01-01
在机器视觉中，对于图像的处理有时候因为放置的原因导致ROI区域倾斜，这个时候我们会想办法把它纠正为正确的角度视角来，本文主要介绍了opencv图像矫正算法，感兴趣的可以了解一下2021-05-05
QLAlchemy是一个强大的ORM（对象关系映射）库，它允许您通过Python代码与关系型数据库进行交互，本文我们将学习如何使用Python和SQLAlchemy库来轻松管理数据库，需要的可以参考下2023-05-05
这篇文章主要介绍了Python自动创建Excel并获取内容,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2020-09-09
这篇文章主要介绍了Python greenlet实现原理和使用示例,greenlet是Python中的一个并行处理库,需要的朋友可以参考下2014-09-09
最新评论