Python对两个有序列表进行合并和排序的例子

 更新时间:2014年06月13日 10:28:56   投稿:junjie   我要评论
这篇文章主要介绍了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

今天栽了个坑,好好反省,就是这样。

相关文章

  • Python配置虚拟环境图文步骤

    Python配置虚拟环境图文步骤

    在本文中我们给大家详细整理了关于Python配置虚拟环境的相关步骤以及图文说明,需要的朋友们学习下。
    2019-05-05
  • 使用 Python 实现微信群友器的思路详解

    使用 Python 实现微信群友器的思路详解

    这篇文章主要介绍了使用 Python 实现微信群友器的思路详解,需要的朋友可以参考下
    2018-09-09
  • Python使用sorted排序的方法小结

    Python使用sorted排序的方法小结

    这篇文章主要介绍了Python使用sorted排序的方法,结合三个实例分析了Python使用sorted方法进行元素排序操作的相关实现技巧,需要的朋友可以参考下
    2017-07-07
  • Python多重继承的方法解析执行顺序实例分析

    Python多重继承的方法解析执行顺序实例分析

    这篇文章主要介绍了Python多重继承的方法解析执行顺序,结合实例形式分析了Python多重继承时存在方法命名冲突情况的解析执行顺序与相关原理,需要的朋友可以参考下
    2018-05-05
  • python实现给微信公众号发送消息的方法

    python实现给微信公众号发送消息的方法

    这篇文章主要介绍了python实现给微信公众号发送消息的方法,结合实例形式分析了Python针对微信公众号接口操作的相关技巧,需要的朋友可以参考下
    2017-06-06
  • 用python登录Dr.com思路以及代码分享

    用python登录Dr.com思路以及代码分享

    如今一般的大学校园或者公寓都是通过客户端来限制路由器使用,基本上都是Dr.com客户端,有的是登录样式,有的是插件样式。下面我们来说说python定制自己的客户端
    2014-06-06
  • 详解Python用三种方式词频的方法

    详解Python用三种方式词频的方法

    这篇文章主要介绍了Python用三种方式词频,每种方法给大家介绍的非常详细,需要的朋友可以参考下
    2019-07-07
  • 基于Python实现的扫雷游戏实例代码

    基于Python实现的扫雷游戏实例代码

    这篇文章主要介绍了基于Python实现的扫雷游戏实例代码,对于Python的学习以及Python游戏开发都有一定的借鉴价值,需要的朋友可以参考下
    2014-08-08
  • Python验证码识别处理实例

    Python验证码识别处理实例

    这篇文章主要介绍了Python验证码识别处理实例,实现过程讲解很详细,感兴趣的小伙伴们可以参考一下
    2015-12-12
  • 单链表反转python实现代码示例

    单链表反转python实现代码示例

    这篇文章主要介绍了单链表反转python实现,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
    2018-02-02

最新评论