概念

归并排序(Merge sort)是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思想是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就向后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

算法步骤

先分再合：
image.png

时间复杂度

  • 最优时间复杂度：O（nlogn）
  • 最坏时间复杂度：O（nlogn）
  • 稳定性：稳定

程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def Merge_sort(alist):
    """
    主要思想就是分治法，先拆分再合并
    整个框架是递归算法，既包括拆解成一个一个的列表，也包列表的缝合
    以为[5,1,3,2,8,7,6,4]例，拆解成[5],[1],[3],[2],[8],[7],[6],[4]
    第一次合并成[1,5],[2,3],[7,8],[4,6]
    第二次合并成[1,2,3,5],[4,6,7,8]
    第三次合并成[1,2,3,4,5,6,7,8]
    :param alist:
    :return: alist.sort
    """
    n = len(alist)
    mid = n //2
    if n <= 1:
        return alist
    left_list = Merge_sort(alist[0:mid])
    right_list = Merge_sort(alist[mid::])
    left_p = 0 # 定义左指针
    right_p = 0 # 定义右指针
    result_list =[]
    while left_p < len(left_list) and right_p < len(right_list):
        if left_list[left_p] < right_list[right_p]:
            result_list.append(left_list[left_p])
            left_p += 1
        else:
            result_list.append(right_list[right_p])
            right_p += 1
    result_list.extend(left_list[left_p::])
    result_list.extend(right_list[right_p::])

    return result_list

总结

主要思想就是分治法，先拆分再合并，整个框架是递归算法，既包括拆解成一个一个的列表，也包列表的缝合。定义两个指针，一个左指针，一个右指针，先比较两个指针指向的的元素大小，将小的元素添加到目标序列中，然后该指针+1继续比较，直到某一个指针走到头，此时将另一个指针指向元素的后面元素全部添加到目标序列中。