[Python知识库]python实现归并排序(merge)

归并排序

1. 算法思想:
   归并排序就是将待排序列不断一分为二,直到分为单个元素作为一个序列,然后向上合并,合并的过程中交换位置,最终合并完成时已经是有序状态了.
   归并排序分为两个过程：
   分裂和归并
   分裂的过程:借鉴二分查找中的分析结果,时间复杂度为O(logn)
   归并的过程:相对于分裂的每个部分,其所有数据项都会被比较和放置一次,所以是线性复杂度,其时间复杂度是O(n)
   综合考虑:每次分裂的部分都进行一次O(n)的数据项归并,总的时间复杂度是O(nlog n)
   归并排序需要额外消耗一倍的存储空间.
2. 实现
   python版本 3.7.2

# 归并排序 python化的归并排序
def merge_Sort(lst):
    # 递归结束条件
    if len(lst) <= 1:
        return lst
    # 分解问题 递归调用
    middle = len(lst) // 2
    left = merge_Sort(lst[:middle])
    right = merge_Sort(lst[middle:])

    # 合并
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(right if right else left)

    return merged


list1 = [1, 5, 4, 2, 23, 15, 2, 45, 56, 7, 8, 9]
print(merge_Sort(list1))

一个可以查看排序演示和较详细介绍的网站
点我查看排序的可视化演示

如有错误还望指出