归并排序Python版

123 4月之前 Python 算法

答案

  1. 将待排序列表从中间位置拆分成2个子列表
  2. 重复1,直至将列表拆分成一个个只有1个元素的小列表
  3. 递归排序两个相邻的小列表,直至所有元素合并完成
def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left = lst[:mid]
    right = lst[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    merged = []
    while len(left) and len(right):
        """
        !!!这里是重点!!!
        因为left和right都是已排序列表,所以循环比较和pop操作后,
        left和right总会有一边先为空列表,而只要其中一边为空列表,
        则另一边里面剩余的元素肯定都比merged中的元素大
        所以把merged和他们(其中一个为空,不会影响结果)
        合并起来就可以拿到排序的结果
        """
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    return merged + left + right

时间复杂度:

  • 最坏:O(n lg n)
  • 平均:O(n lg n)
  • 最好:O(n lg n)