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

yipeiwu_com5年前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 列表、字典和集合的添加和删除操作

在python中,元组不可变,只能查询不能修改,列表、字典和集合的基本操作,各不相同,下面就来比较一下它们的添加和删除操作吧。 添加 一、列表 1.“+”号 #两个数组相加,生成一个...

python 输出列表元素实例(以空格/逗号为分隔符)

给定list,如何以空格/逗号等符号以分隔符输出呢? 一般的,简单的for循环可以打印出list的内容: l=[1,2,3,4] for i in l: print(i) 输出结...

Python图形绘制操作之正弦曲线实现方法分析

Python图形绘制操作之正弦曲线实现方法分析

本文实例讲述了Python图形绘制操作之正弦曲线实现方法。分享给大家供大家参考,具体如下: 要画正弦曲线先设定一下x的取值范围,从0到2π。要用到numpy模块。 numpy.pi 表示...

Python 实现中值滤波、均值滤波的方法

Python 实现中值滤波、均值滤波的方法

红包: Lena椒盐噪声图片: # -*- coding: utf-8 -*- """ Created on Sat Oct 14 22:16:47 2017 @author:...