归并排序python实现

2019-04-11 10:08:39来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 

归并排序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