Python全系列 教程
3567个小节阅读:5930.1k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
归并排序(Merge sort)是一种基于分治策略的排序算法,包含"划分"和"合并"2个阶段
划分阶段:通过递归不断地将数组从中点处分开,将长数组的排序问题转换为短数组的排序问题
合并阶段:当子数组长度为 1 时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束
它的核心思想是:先分后归(先拆分为一个个有序的子序列,再将一个个有序子序列进行归并操作最后合并为一个有序的序列)
把长度为n的输入序列分成两个长度为n/2的子序列,直到每个数字分为一组;
将若干个组两两合并,保证合并后的组是有有序的;
重复第2步操作直到只剩一组,排序完成
xxxxxxxxxx
def 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