python 实现·十大排序算法之归并排序 (Merge Sort)

关注

发布于: 2020 年 05 月 25 日

简介﻿
归并排序(Merge Sort)是一种非常高效的排序方式，它用了分治的思想，基本排序思想是：先将整个序列两两分开，然后每组中的两个元素排好序。接着就是组与组和合并，只需将两组所有的元素遍历一遍，即可按顺序合并。以此类推，最终所有组合并为一组时，整个数列完成排序。
算法实现步骤﻿
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用递归的进行排序；
将两个排序好的子序列的元素拿出来，按照顺序合并成一个最终的序列，即可完成排序。
Python 代码实现﻿
# merge_sort 代码实现
from typing import List
def merge(arr1:List[int], arr2:List[int]): 
    result = []
    while arr1 and arr2:
        if arr1[0] < arr2[0]:
            result.append(arr1.pop(0))
        else:
            result.append(arr2.pop(0))
    if arr1:
        result += arr1
    if arr2:
        result += arr2
    return result
def merge_sort(arr:List[int]):
    """
    归并排序
    :param arr: 待排序的List
    :return: 排好序的List
    """
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
﻿
# 测试数据
if __name__ == '__main__':
    import random
    random.seed(54)
    arr = [random.randint(0,100) for _ in range(10)]
    print("原始数据：", arr)
    arr_new = merge_sort(arr)
    print("归并排序结果：", arr_new)
﻿
# 输出结果
原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
归并排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
动画演示
算法分析时间复杂度
归并排序时间复杂度计算公式：排序总时间=子序列排序时间+合并时间。
假设一个序列有n个数的排序时间为T(n)，那么
T(n)=2T(2n​)+合并时间
由于合并时，两个子序列已经组内排好序了，将两个排好序的序列组合成一个大的有序序列，时间复杂度为n，则有：
T(n)=2T(2n​)+n
递归推导可得出：
T(n)=2mT(2mn​)+mn
当2mn​=1时，递归结束，此时有：
T(1)=0,T(n)=nlog2​n
所以归并排序的时间复杂度为O(nlog2​n)。
空间复杂度
每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2​n)，但每次递归都会释放掉所占的辅助空间，下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度为O(n)。
稳定性
归并排序过程中，能保证相等元素相对位置保持不变，因此为稳定排序。
综合评价
联系我们﻿
个人博客网站：http://www.bling2.cn/
Github地址：https://github.com/lb971216008/Use-Python-to-Achieve
知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve
小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve
博客园：https://www.cnblogs.com/Use-Python-to-Achieve
﻿
﻿