Python对两个有序列表进行合并和排序的例子
作者:junjie 时间:2022-06-07 00:11:37
假设有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,有序列表,合并,排序
0
投稿
猜你喜欢
python 插入Null值数据到Postgresql的操作
2021-11-24 22:39:24
详解Python中的null是什么
2022-11-30 15:33:56
yolov5训练时参数workers与batch-size的深入理解
2021-08-01 04:50:20
浅谈在js传递参数中含加号(+)的处理方式
2024-05-13 09:18:56
Go语言break跳转语句怎么使用
2024-05-28 15:37:12
总结分析Python的5个硬核函数
2022-04-12 11:05:42
python 基于Appium控制多设备并行执行
2022-12-11 12:00:06
Python中关于列表的常规操作范例以及介绍
2023-02-20 12:44:44
利用Python实现简单的Excel统计函数
2021-09-27 09:21:09
python 返回一个列表中第二大的数方法
2022-06-01 00:17:47
golang API请求队列的实现
2024-03-11 16:39:50
mysql 动态执行存储过程语句
2024-01-27 01:54:38
在JavaScript中调用Java类和接口的方法
2024-04-10 10:42:49
django 连接数据库 sqlite的例子
2023-08-03 19:03:15
Python机器学习应用之基于天气数据集的XGBoost分类篇解读
2023-09-12 05:45:07
CentOS安装mysql5.7 及简单配置教程详解
2024-01-21 08:18:51
Python中的self用法详解
2023-08-22 15:34:19
JavaScript字符串对象toLowerCase方法入门实例(用于把字母转换为小写)
2024-05-08 10:10:47
Opera浏览器简介
2009-02-05 20:56:00
python 递归遍历文件夹,并打印满足条件的文件路径实例
2023-08-07 07:22:48