【 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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

Making Things See

Making Things See

Greg Borenstein / Make / 2012-2-3 / USD 39.99

Welcome to the Vision Revolution. With Microsoft's Kinect leading the way, you can now use 3D computer vision technology to build digital 3D models of people and objects that you can manipulate with g......一起来看看 《Making Things See》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具