分而治之

Snipaste_2020-04-09_23-37-28


归并排序

算法图解

Snipaste_2020-04-09_23-39-54
Snipaste_2020-04-09_23-44-01

分解成数组长度为1时,两两合并,分别取出最小的元素放置在前面

Snipaste_2020-04-09_23-47-37
Snipaste_2020-04-09_23-47-25

伪代码

Snipaste_2020-04-09_23-54-38
Snipaste_2020-04-10_02-04-24

Snipaste_2020-04-10_00-01-12 A[left...right]表示A数组中left下标到right下标中的数,e.g. A[left+k...right]代表A数组中left+k下标到right下标中的数。

代码实例

def Msort(A, left, right):
    # left为子数组开始下标,right子数组结束下标,
    # mid为(left + right)/2 向下取整,即为子数组中间的位置
    if left >= right:
        return      # 分成数组长度为1的子数组时,结束递归
    mid = int((left + right) / 2)
    Msort(A, left, mid)
    Msort(A, mid + 1, right)
    Merge(A, left, mid, right)
    return

def Merge(A, left, mid, right):
    B = A[:]        # Python数组深拷贝
    k = 0           # Merge合并数组的下标
    i = left        # Left左子数组的下标
    j = mid + 1     # Right右子数组的下标

    #取左右子数组中最小的元素置于合并数组中,当有一边数组遍历完全后结束
    while i <= mid and j <= right:
        if B[i] <= B[j]:    # 取左边
            A[left + k] = B[i]
            i += 1
            k += 1
        else:               #取右边
            A[left + k] = B[j]
            j += 1
            k += 1

    # 将另一边未遍历完的数组中的元素添加到合并数组中
    # 当子数组开始下标+合并数组下标大于子数组结束下标时,即所有元素填充完毕,循环结束
    while left + k <= right:
        if i <= mid:        # 填充左边的子数组中的元素
            A[left + k] = B[i]
            i += 1
        elif j <= right:    # 填充右边的子数组中的元素
            A[left + k] = B[j]
            j += 1
        k += 1

    return

算法复杂度分析

Snipaste_2020-04-10_19-09-47.png

递归树法分析复杂度 简单直观

Snipaste_2020-04-10_19-25-34