归并排序

概念与原理

归并排序的思想是先拆分，再组合，组合的同时进行排序，最后组合成一个新的有序序列

拆分，将序列拆到每一份只有一个元素

合并，合并的顺序是怎么拆的怎么合，比如由[54, 26]拆成了[54]，[26]，合并的时候就是他们两个合，54对应一个left_pointer游标，26对应right_pointer游标，比较两个游标对应元素的大小，若左边比右边大，则left_pointer与right_pointer对应的元素互换

游标进行互换操作之后均需要往后移一位，直到移到最后，将未移完的一侧的所有元素放到新序列的后面

重复这样的融合过程，直到融合为一个序列，此时序列为有序序列

实现

def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:  # 当拆分拆分拆到序列中只有一个元素时，返回这个序列
        return alist
    mid = n // 2

    # left 采用归并排序后形成的新的有序列表
    left_li = merge_sort(alist[:mid])

    # right 采用归并排序后形成的新的有序列表
    right_li = merge_sort(alist[mid:])

    # 将两个有序子序列合并成一个新的整体
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []

    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] >= right_li[right_pointer]:
            result.append(right_li[right_pointer])
            right_pointer += 1
        else:
            result.append(left_li[left_pointer])
            left_pointer += 1

    # 跳出循环时，有一个游标指向了拆分列表的最后一位的下一位（这一位不存在，但是循环时加到了下一位），需要将另一个序列剩余的所有元素加到result中
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result


if __name__ == "__main__":
    li = [66, 22, 55, 44, 11, 99, 77, 33, 88]
    print(li)
    merge = merge_sort(li)
    print(li)
    print(merge)
    
# 运行结果：
# [66, 22, 55, 44, 11, 99, 77, 33, 88]
# [66, 22, 55, 44, 11, 99, 77, 33, 88]
# [11, 22, 33, 44, 55, 66, 77, 88, 99]

归并排序的时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定

在进行归并排序的时候，无所谓最坏还是最优情况，一视同仁，所有情况都需要走一遍，因此时间复杂度都是nlogn，以2为底

常见排序算法效率比较

一定需要掌握的是快速排序，它的时间复杂度更趋近于nlogn，且不需要像归并排序一样拿出一块内存单独的地方来进行存储

剩下的任意掌握一两种即可（要会原理，要会把算法写出来）