Python对两个有序列表进行合并和排序的例子
作者:junjie 发布时间:2022-06-07 00:11:37
标签: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
这真的只能处理一个元素的情形,还不能解决问题,不过好歹我们有一个大概的思路了。如果有列表中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
今天栽了个坑,好好反省,就是这样。


猜你喜欢
- 排序是个很泛的概念,而且根据被排序的数据量排序方法和侧重又有很大的不同。因此一直没想到从何着手。今天把玩iphone的时候突然又想到这个问题
- 一、Cookie原理HTTP是无状态的面向连接的协议, 为了保持连接状态, 引入了Cookie机制Cookie是http消息头中的一种属性,
- 我们要生成二维码都需要借助一些类库来实现了,下面我介绍利用PHP QR Code生成二维码吧,生成方法很简单,下面我来介绍一下.利用php类
- 本文意在弄清楚这些概念间的关系及其作用。弄清Mysql在开启事务的情况下,每条sql执行时的加锁操作和MVCC版本控制。为使讨论简单,本文忽
- mssql 错误日志文件存放位置:C:\Program Files\Microsoft SQL Server\MSSQL\LOG 用记事本查
- 1.简介在编写代码时,往往涉及时间、日期、时间戳的相互转换。2.示例# 引入模块import time, datetime2.1 str类型
- 本文实例分析了Python自定义进程池。分享给大家供大家参考,具体如下:代码说明一切:#encoding=utf-8#author: wal
- 1、简要说明结巴分词支持三种分词模式,支持繁体字,支持自定义词典2、三种分词模式全模式:把句子中所有的可以成词的词语都扫描出来, 速度非常快
- 看代码吧~predict = output.argmax(dim = 1)confusion_matrix =torch.zeros(2,2
- 当今,有一点可以肯定的是,设计的领域在扩大,这是一个需要设计的世界。拒最新的统计资料显示,中国目前已有正规的设计学院教学机构700多所,并且
- 引言软件开发经历了许多阶段,如需求收集和分析、设计、软件开发、测试和发布。测试是 SDLC 不可或缺的一部分,单元测试是一种可靠的测试类型。
- 一、语法错误异常:大多数的异常都不会被程序处理,都以错误信息的形式展现在这里二、异常处理while True: t
- 我们先用 new 关键字 来创建一个ArrayList 对象,给数组的item赋值,把数组初
- 1、查找表中多余的重复记录,重复记录是根据单个字段(peopleId)来判断select * from peoplewhere people
- python中使用pip安装扩展包的时候,有时候会遇到如下类似报错:Running setup.py install for mysqlcl
- 这个坐标轴变名用法,我真服气了,我在网上看大家写的教程,看的头晕,也没看懂他们写xtick到底怎么用的,最后找到官方教程,看了一个例子,ov
- Node被设计用来高效的处理I/O操作,但是你应该知道,有些类型的程序并不适合这种模式。比如,如果你打算用Node处理一个CPU密集的任务,
- 最近一直在做Dnn模块的开发,过程中碰到这么一个问题,需要同时插入N条数据,不想在程序里控制,但是SQL Sever又不支持数组参数.所以只
- 3. 品味“决定”艺术作品的好坏,设计的好坏则来自主观意见我们在鉴赏艺术作品时,用看法来表达当时的感觉,而你的品味则会左右你的看法。以一个有
- CookieHTTPHTTP(Hyper Text Transfer Protocol,超文本传输模式)属于无状态协议,在同一个连接中,两个