算法原理:
改归并排序将序列折半分成两个子序列,然后继续拆分,直到每个序列只有一个数据时,再将各个子序列排序后合并叠加。直到所有子序列都合并,排序完成。该算法采用分治的思想。
图解算法思路:
编辑
编辑
编辑
编辑
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)
![点击并拖拽以移动](/i/l/?n=22&i=blog/2986421/202210/2986421-20221021212903047-620102406.gif)