Day 20 归并排序算法

Day 19 合并两个有序数组作业总结

合并两个有序数组

利用两个数组原本已经有序的特点：

def merge(left, right):
    i = 0
    j = 0
    temp = []
    while i <= len(left) - 1 and j <= len(right) - 1:
        if left[i] <= right[j]:
            temp.append(left[i])
            i += 1
        else:
            temp.append(right[j])
            j += 1
    temp += left[i:] + right[j:]
    return temp

print(merge([1,3,4],[2,3,3])) 

思路可参考示意图：

Day20 写出归并排序算法

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序算法的核心正是 Day 19 的合并两个有序数组，补全如下代码：

def merge_sort(lst):
    #
    #
    #
    return lst_sorted

归并排序两阶段：

先分，直到长度1，然后再合：

归并排序的详细讲解，可参考：https://www.programiz.com/dsa/merge-sort