目录Python全系列 教程
3567个小节阅读：5929.1k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
归并排序（Merge sort）是一种基于分治策略的排序算法，包含"划分"和"合并"2个阶段
划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束
它的核心思想是：先分后归（先拆分为一个个有序的子序列，再将一个个有序子序列进行归并操作最后合并为一个有序的序列）
把长度为n的输入序列分成两个长度为n/2的子序列，直到每个数字分为一组；
将若干个组两两合并，保证合并后的组是有有序的；
重复第2步操作直到只剩一组，排序完成
xxxxxxxxxxdef merge_sort(lists): # 如果要需要归并排序的列表长度少于1,无法分割,直接返回 if len(lists) <=1: return lists # 设置要分割的索引 num = int(len(lists) / 2) # 分割 left = merge_sort(lists[:num]) right = merge_sort(lists[num:]) # 合并left+ right return merge(left,right)def merge(left,right): rs = [] l,r = 0,0 # 判断是否有需要根据排序添加数据 while l<len(left) and r<len(right): # 从小到大排序，谁小谁加到rs里 if left[l] <= right[r]: rs.append(left[l]) # 向后挪一个索引 l += 1 else: rs.append(right[r]) r += 1 # 拼接上剩余没有比较的元素 rs += list(left[l:]) rs += list(right[r:]) return rs
if __name__ =='__main__': nums = [5,2,6,4,7,3,1] tmp = merge_sort(nums) print(tmp)时间复杂度 $ O( n \log n )$、非自适应排序：划分产生高度为 $ \log n$ 的递归树，每层合并的总操作数量为 $ n $ ，因此总体时间复杂度为 $ O (n \log n)$
空间复杂度 $ O ( n ) $、非原地排序：递归深度为 $ \log n $ ，使用 $ O (\log n) $ 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 $ O(n) $大小的额外空间
稳定排序：在合并过程中，相等元素的次序保持不变
实时效果反馈
1. 关于归并排序算法，说法正确的是？
A 归并排序需要将数列分成若干个子序列，在合并时排序
B 归并排序每一轮都要俩俩比较元素
C 归并排序只需要分2次数列即可
D 归并排序分完数据，数据就是有有序的，直接合并即可
答案
1=>A