归并排序python实现

2023-01-31 00:01:48 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)

 

相关文章