专栏首页未闻Code一日一技:如何更好地理解归并排序?

一日一技:如何更好地理解归并排序?

摄影:产品经理

厨师:kingname

请确保你已经看了我昨天的公众号文章。昨天的内容是今天的基础。

一日一技:在 Python 里面如何合并多个有序列表并使得结果依然有序?

在昨天的文章里面,我们已经知道,可以使用 heapq.merge把两个有序列表合并成新的有序列表。

现在,我们来设计一个排序算法,对列表:[1,4,2,0,4,5,1,-3,-8,188,34] 进行排序。

我们现在先把列表拆分成a列表:[1,4,2,0,4,5]和b列表 [1,-3,-8,188,34]。如果我们能够分别让这两个列表各自有序,然后应用昨天的方法,合并一下,最终结果自然就出来了。

那么如何让这两个列表各自有序呢?我们以 [1,4,2,0,4,5]为例。继续把它拆分为两个列表 [1,4,2][0,4,5]。只要这两个列表各自有序,那么合并一下就行了。

我们再来看 [1,4,2],如何让它有序呢?我们继续分成两个列表 [1][4,2]。显然只有一个元素的列表 [1]是有序的。

再来看 [4,2],继续分成两个列表 [4][2]。这两个列表都只有一个元素,所以他们都是有序的。此时对他们进行合并,得到 [2,4]

[1][2,4]合并,得到 [1,2,4]

[1,2,4][0,4,5]合并,得到 [0,1,2,4,4,5]

[0,1,2,4,4,5][-8,-3,1,34,188]合并,得到 [-8,-3,0,1,1,2,4,4,5,34,188]

排序完成。

整个过程先拆分再合并,这种排序算法叫做 归并算法。它的时间复杂度始终是 O(nlogn)。而我们常常听说的快速排序,只有在最好的情况下时间复杂度才能达到 O(nlogn)。所以归并排序在时间复杂度这个角度是优于快速排序的。

那么如何使用代码来实现呢?合并的部分请看昨天的文章,今天我们主要描述拆分的逻辑:

import heapq

def sort(target):
    if not target:
        return []
    if len(target) == 1:
        return target
    left = target[:len(target) // 2]
    right = target[len(target)//2 :]
    sorted_left = sort(left)
    sorted_right = sort(right)
    result = heapq.merge(sorted_left, sorted_right)
    return result

运行效果如下图所示:

未闻Code

PYTHON干货日更

本文分享自微信公众号 - 未闻Code(itskingname),作者:kingname

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用图像识别来自动确认网页加载成功

    在对安卓手机设计自动化测试用例的时候,判断一个测试场景是否可以自动化的依据在于其是否需要人的参与。对于wifi能否自动打开关闭,短信能否自动收发这样的场景,不需...

    青南
  • Python的单元测试(一)

    测试驱动的软件开发方式可以强迫程序员在开发程序的时候使程序的函数之间实现高内聚,低耦合。这样的方式可以降低函数之间的依赖性,方便后续的修改,增加功能和维护。

    青南
  • 算法题:把列表右侧 k 位数依次移动到左侧

    给定一个非空列表和一个非负整数 k,把列表右侧的 k 位依次移动到左侧。例如:[1, 2, 3, 4, 5, 6],n 为3,则移动以后,变为:[4, 5, 6...

    青南
  • PYTHON 自动化运维 -- 绘制数据库表空间变化图

    已oracle为例(sql语句见文末:根据自己的修改,比如PDB名字,保存的位置等):

    大大刺猬
  • 用飞桨做自然语言处理:神经网络语言模型应用实例

    语言模型的身影遍布在NLP研究中的各个角落,想要了解NLP领域,就不能不知道语言模型。

    代码医生工作室
  • 用飞桨做自然语言处理:神经网络语言模型应用实例

    语言模型的身影遍布在NLP研究中的各个角落,想要了解NLP领域,就不能不知道语言模型。

    量子位
  • 如何用飞桨实现 Bengio 经典神经网络语言模型?

    刚入门深度学习与自然语言处理(NLP)时,在学习了 Goldberg 特别棒的入门书 NN4NLP,斯坦福 cs224n 等等后,也无限次起念头,写个系列吧,但...

    用户1386409
  • Bengio 团队力作:GNN 对比基准横空出世,图神经网络的「ImageNet」来了

    图神经网络(GNN)是当下风头无两的热门研究话题。然而,正如计算机视觉的崛起有赖于 ImageNet 的诞生,图神经网络也急需一个全球学者公认的统一对比基准。

    AI科技评论
  • Redis 一二事(2) - 在spring中使用jedis 连接调试单机redis以及集群redis

    Redis真是好,其中的键值用起来真心强大啊有木有, 之前的文章讲过搭建了redis集群 那么咋们该如何调用单机版的redis以及集群版的redis来使用缓存...

    风间影月
  • 基于Casbin的Docker权限管理访问控制插件

    Docker是目前主流的一种容器技术。为了解决多用户同时访问Docker时产生的安全问题,Docker设计了访问控制插件(Authorization Plugi...

    FB客服

扫码关注云+社区

领取腾讯云代金券