数据结构与算法 8.归并排序 mergeSort

归并排序 mergeSort

把序列按长度分成两个子序列,每个子序列再次分解,重复以上操作直至无法分解(递归从外到内的过程)
把两个最小单位的子序列按条件归并成一个新序列,新序列继续和同一层的序列归并(递归从内到外的过程)
使用两个指针从被归并的两个序列中分别取值比较大小,取出满足条件的值并移动该指针,然后进行下一次比较
利用map()、reduce()进行拆解和合并的过程
需要消耗大量空间

复杂度:最优时间复杂度:O(nlogn)
        最差时间复杂度:O(nlogn)
        稳定性:稳定
def merge_sort(varlist):
    # 结束递归的条件,子序列被分解为单个元素
    if len(varlist) <= 1 :
        return varlist

    # 1.第一步:把完整的序列分解为单个元素的序列,然后作为参数调用归并两两排序

    # 将序列按长度等分
    num = len(varlist) // 2
    l_left = varlist[:num]
    l_right = varlist[num:]

    # 分解后的两个子序列调用自身继续分解,直至被分解为单个元素
    left = merge_sort(l_left)
    right = merge_sort(l_right)

    # 当出现left和right都为单个元素时,递归从外向内的过程结束,开始归并
    return merge(left,right)

def merge(left,right):
    # 2.第二步:从传入的两个序列中,按顺序各取出一个元素比较大小
    # 把满足排序条件的取出放入空list,不满足的等待下一次比较,直至任一序列中元素被取完

    # l和r指针用来标记从left和right中取值的位置
    l,r = 0,0
    # 空list用来存放排序后的结果,排序完成则return
    reslist = []

    # l增加到与left长度相等,或r增加到与right长度相等,表示该序列被遍历完成,结束循环
    while l < len(left) and r < len(right) :

        # 从两个序列中各取出一个值进行比较,把满足条件的放入新序列,并移动指针
        if left[l] < right[r] :
            reslist.append(left[l])
            l += 1
        else :
            reslist.append(right[r])
            r += 1

    # 把另一序列中剩余的元素全部添加到新序列
    # 此时另一个序列中无论剩余多少元素没被取出,都一定是在前一层归并中排好序的
    reslist += left[l:]
    reslist += right[r:]

    return reslist

varl = [5,1,7,5,6,3,4,8,2,3,5,9]
res = merge_sort(varl)
print(res)

[1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9]
上一篇:数据结构与算法 11.归并排序 mergeSort


下一篇:【LeetCode】300.最长递增子序列——暴力递归(O(n^3)),动态规划(O(n^2)),动态规划+二分法(O(nlogn))