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
今天栽了个坑,好好反省,就是这样。
0
投稿
猜你喜欢
- //关闭,父窗口弹出对话框,子窗口直接关闭this.Response.Write("<script language=jav
- function commafy() { var num = document.getElementById("NumA"
- →问题提出:我用dw做了一个下拉菜单,但是碰到form的列表项就跑到下面去了,请帮忙解决,先谢谢各位了!请看问题图示如下:→解决问题:由于层
- 如何做一个密码“生成器”?randompassword.asp<% Dim i, intNum,&nbs
- 本文实例讲述了CentOS 6/7环境下通过yum安装php7的方法。分享给大家供大家参考,具体如下:安装php7已经是现在linux服务器
- CURLOPT_RETURNTRANSFER 选项:curl_setopt($ch, CURLOPT_RETURNTRANSFER,1);如
- 当然这应该属于正常过滤手法,而还有一种过滤HTML标签的最终极手法,则是将一对尖括号及尖括号中的所有字符均替换不显示,该方法对于内容中必须描
- 这篇论坛文章(赛迪网技术社区)主要介绍了一些特别有用但文档中没有介绍的sql server DBCC命令,详细内容请参考下文:以下是一些sq
- 网站或应用的登录页面有时候通常用户会看很多遍,同时也有机会诱使临时用户注册,所以,一个设计良好的登录页面会比你想象的更有用。这里是一些我们收
- 这段程序的方法是利用XMLHTTP来读取腾讯网站的相应HTML代码获取QQ的头像,根据这个想法,我们还
- 学了几天正则,差不多该总结整理写成果了,之前就想写语法高亮匹配来着,不过水平不够,看着例子都不理解。那么我们来分析下两位大神 次碳酸钴 和
- 目录1.事件循环2.协程和异步编程2.1 基本使用2.2 await2.3 Task对象1.事件循环可以理解成为一个死循环,去检查任务列表中
- 等值线图的Python绘制方法等值线图或等高线图在科学界经常用到,它是由一些封闭的曲线组成的,来表示三维结构表面。虽然看起来复杂,其实用ma
- 本文实例讲述了PHP字典树(Trie树)定义与实现方法。分享给大家供大家参考,具体如下:Trie树的概念(百度的解释):字典树又称单词查找树
- PHP并非不能实现HTTP服务,一般来讲,这叫网络编程或Socket编程。在学习到其他语言的这部分的时候,一般的思路就是如何监听TCP实现一
- 本文实例讲述了Python3实现从文件中读取指定行的方法。分享给大家供大家参考。具体实现方法如下:# Python的标准库linecache
- 在我们设计网页的时候,总会遇到一些不愉快的事情,最常见的莫过于在后台添加内容后才发现显示的页面被撑开,导致网页极度不美观。以前大
- 在工作之余抽了点时间写了一下这个,在ie6-ie7-ff下显示位置基本都一致了。(发现demo页面用栅格线做背景,调试还真的容易得多 。热力
- 1.collections模块collections模块自Python 2.4版本开始被引入,包含了dict、set、list、tuple以
- login <?php require "../include/DBClass.php"; $usern