【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort

栏目: Python · 发布时间: 6年前

内容简介:【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort

【归并排序】这里我们利用递归算法不断地将列表一分为二,base case就是列表中没有元素或者只剩一个元素,因为此时这个子列表必然是正序的;然后再逐步把两个 排序 完成的子列表合并成一个新的正序列表,直到所有元素排序完毕。

【示意图】这是一个从下至上的过程(Bottom-Up)

将列表不断从中间分成两个子列表,直到到达最底部,子列表中只有一个元素

【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort

然后,从下至上不断合并两个子列表,将两个子列表的所有元素排序形成一个新的列表。

【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort

【 implementation of merge sort 】

【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort

可以利用print查看每一步做了哪些操作。

【 performance analysis 】

时间复杂度是O(n*log n);但是合并的过程需要多余的空间,空间复杂度为O(n)。


以上所述就是小编给大家介绍的《【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

UNIX环境高级编程

UNIX环境高级编程

W.Richard Stevens、Stephen A.Rago / 尤晋元、张亚英、戚正伟 / 人民邮电出版社 / 2006年 / 99.00元

本书是被誉为UNIX编程“圣经”的Advanced Programming in the UNIX Environment一书的更新版。在本书第1版出版后的十几年中,UNIX行业已经有了巨大的变化,特别是影响UNIX编程接口的有关标准变化很大。本书在保持了前一版风格的基础上,根据最新的标准对内容进行了修订和增补,反映了最新的技术发展。书中除了介绍UNIX文件和目录、标准I/O库、系统数据文件和信息......一起来看看 《UNIX环境高级编程》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

在线进制转换器
在线进制转换器

各进制数互转换器