归并排序python实现
2019-04-11 10:08:39来源:博客园 阅读 ()
归并排序python实现
归并排序
归并排序在于把序列拆分再合并起来,使用分治法来实现,这就意味这要构造递归算法
首先是一个例子
原序先通过一半一半的拆分,然后:
然后再一步一步的向上合并,在合并的过程中完成了排序,合并排序算法如下:
def merge(s1,s2,s):
"""将两个列表是s1,s2按顺序融合为一个列表s,s为原列表"""
# j和i就相当于两个指向的位置,i指s1,j指s2
i = j = 0
while i+j<len(s):
# j==len(s2)时说明s2走完了,或者s1没走完并且s1中该位置是最小的
if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
s[i+j] = s1[i]
i += 1
else:
s[i+j] = s2[j]
j += 1
这是以列表为例,道理其实很简单,因为两个序列是排好序的,所以都从左往右,互相比较选择较小的那个数放入最后的序列,s是原序列,所以在一开始会有与len(s)的比较
完整算法
算法中通过递归并调用merge函数完成排序
def merge(s1,s2,s):
"""将两个列表是s1,s2按顺序融合为一个列表s,s为原列表"""
# j和i就相当于两个指向的位置,i指s1,j指s2
i = j = 0
while i+j<len(s):
# j==len(s2)时说明s2走完了,或者s1没走完并且s1中该位置是最小的
if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
s[i+j] = s1[i]
i += 1
else:
s[i+j] = s2[j]
j += 1
def merge_sort(s):
"""归并排序"""
n = len(s)
# 剩一个或没有直接返回,不用排序
if n < 2:
return
# 拆分
mid = n // 2
s1 = s[0:mid]
s2 = s[mid:n]
# 子序列递归调用排序
merge_sort(s1)
merge_sort(s2)
# 合并
merge(s1,s2,s)
if __name__ == '__main__':
s = [1,7,3,5,4]
merge_sort(s)
print(s)
时间复杂度
还拿这个图说
这个图显然是二叉树的形式,所以若集合有n个元素,那高度就为log(n)
但其实在每一层做比较的时候,都是一个一个的向序列中放小的元素,每一层都是要放n次
所以时间复杂度为nlog(n)
原文链接:https://www.cnblogs.com/sfencs-hcy/p/10600197.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:基础知识补充-3.13
下一篇:轻量的web框架Bottle
- python3基础之“术语表(2)” 2019-08-13
- python3 之 字符串编码小结(Unicode、utf-8、gbk、gb2312等 2019-08-13
- Python3安装impala 2019-08-13
- 小白如何入门 Python 爬虫? 2019-08-13
- python_字符串方法 2019-08-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash