归并排序

难度：⭐⭐⭐⭐

1. 题目描述

题目描述

• 归并排序（Merge sort）算法是采用分治法（先分割，再合并）的一个非常典型的应用
• 递归法步骤：
  1. 【分割】将序列从中一分为二
  2. 【分割】对上述两个子序列分别一分为二，一直重复直到无法分割为止（子序列长度为 1）
  3. 【合并】对两个子序列按照顺序进行合并，一直重复直到变成一个序列

2. 关键点

• 先分割，再合并

3. 代码实现

点击显示代码

import random


def sort_merge(lst):
    """归并排序"""
    if len(lst) < 2:
        return lst
    mid = len(lst) // 2
    left = sort_merge(lst[:mid])
    right = sort_merge(lst[mid:])

    i = j = 0
    lst2 = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            lst2.append(left[i])
            i += 1
        else:
            lst2.append(right[j])
            j += 1

    while i < len(left):
        lst2.append(left[i])
        i += 1

    while j < len(right):
        lst2.append(right[j])
        j += 1

    return lst2


lst = [random.randint(0, 10) for i in range(10)]
print(lst)
lst2 = sort_merge(lst)
print(lst2)

4. 运行示例

[6, 1, 0, 9, 3, 7, 1, 5, 8, 10]
[0, 1, 1, 3, 5, 6, 7, 8, 9, 10]

5. 进阶思考

1. 优化示例代码