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