python系列归并排序图文详解

标签：归并 python lst 编辑 算法 序列 排序 图文

​

 算法原理：

       改归并排序将序列折半分成两个子序列，然后继续拆分，直到每个序列只有一个数据时，再将各个子序列排序后合并叠加。直到所有子序列都合并，排序完成。该算法采用分治的思想。

图解算法思路：

​编辑

 

​编辑

 

​编辑

 

​编辑

def merge_sort(lst):
    if len(lst) <= 1:
        return lst  # 从递归中返回长度为1的序列

    middle = len(lst) // 2
    left = merge_sort(lst[:middle])  # 通过不断递归，将原始序列拆分成n个小序列
    right = merge_sort(lst[middle:])
    print("left",left)
    print("right", right)
    return merge(left, right)

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):  # 比较传入的两个子序列，对两个子序列进行排序
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])  # 将排好序的子序列合并
    result.extend(right[j:])
    return result

a = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
lst = merge_sort(a)
print(lst)

 

​

标签：归并,python,lst,编辑,算法,序列,排序,图文
From： https://www.cnblogs.com/qingshaonianbiancheng/p/16814831.html