当前位置:网站首页>空间复杂度为O(1)的归并排序
空间复杂度为O(1)的归并排序
2022-08-10 00:54:00 【qnner】
前言
最近楼主在刷算法题目,刷到了归并排序。自己简单实现后,再次跟常见的归并排序比较,发现空间复杂度更低。所以记录本文用于比较两种算法的实现方式。
经典实现方式:空间复杂度O(n)
这里不再赘述,贴一篇牛客网写的比较详细的帖子:https://www.nowcoder.com/discuss/968849?type=all&order=recall&pos=&page=1&ncTraceId=&channel=-1&source_id=search_all_nctrack&gio_id=8AD3C350B55856EAFE45974949E1359F-1660059896728
复杂度分析:
- 时间复杂度 NlogN
- 空间复杂度 O(N)
我的实现
思路
重点是merge函数。merge函数的作用是合并两个已经排序的数组。我这里的大致思路是,将其中一个数组作为基,把另外一个数组的每一个元素都插入到这个基里面去。
代码实现
def cmp(left, mid):
return left > mid
def merge(arr, left, mid, right):
while mid < right:
for move_left in range(left, mid):
if cmp(arr[move_left], arr[mid]):
tmp = arr[move_left]
for i in range(move_left, mid):
arr[move_left] = arr[i + 1]
arr[i + 1] = tmp
tmp = arr[move_left]
left = move_left
break
mid += 1
def merge_sort(arr, l=None, r=None):
if l is None:
l = 0
if r is None:
r = len(arr)
if l == r -1:
return arr
else:
mid = int((l + r) / 2)
merge_sort(arr, l, mid)
merge_sort(arr, mid + 1, r)
merge(arr, l, mid, r)
if __name__ == '__main__':
arr = [12, 2, 3]
merge_sort(arr)
print(arr)
可以看见,在merge的时候,并没有使用额外的数组空间,所以空间复杂度为O(1)
边栏推荐
- GB28181 sip和RTSP(Real-Time Streaming Protocol)实时流控制协议
- 【Swoole系列3.5】进程池与进程管理器
- The shell specifies the parameter name to pass the parameter
- 不是吧,连公司里的卷王写代码都复制粘贴,这合理?
- R语言使用coxph函数构建生存分析回归模型,使用forestmodel包的forest_model函数可视化生存回归模型对应的森林图
- Qt的pro文件递归搜寻添加文件
- Prometeus 2.31.0 新特性
- 以太网PHY芯片LAN8720A芯片研究
- 开发IM即时通讯容易吗?需要什么技术
- Initial attempt at UI traversal
猜你喜欢
assert利用蚁剑登录
Penetration Testing and Offensive and Defense Confrontation - Vulnerability Scanning & Logic Vulnerability (Part1)
基于Web的疫情隔离区订餐系统
这一次,话筒给你:向自由软件之父 Richard M. Stallman 提问啦!
Research on Ethernet PHY Chip LAN8720A Chip
【论文笔记】基于深度学习的机器人抓取虚拟仿真实验教学系统
OpenSSF的开源软件风险评估工具:Scorecards
【kali-密码攻击】(5.1.2)密码在线破解:Medusa
什么是一网统管?终于有人讲明白了
ITK编译remote库
随机推荐
Web性能测试模型小结
分析 20 个 veToken 生态系统协议 这种代币模型为何受欢迎?
R语言使用glm函数构建logistic回归模型,使用forestmodel包的forest_model函数可视化逻辑回归模型对应的森林图
微信账户体系科普:什么是UnionId、OpenId与wxopenid?
ASEMI整流桥GBJ1010参数,GBJ1010规格,GBJ1010封装
小程序中计算距离信息
Unity reports Unsafe code may only appear if compiling with /unsafe. Enable “Allow ‘unsafe’ code” in Pla
assert利用蚁剑登录
OpenSSF的开源软件风险评估工具:Scorecards
eyb:Redis学习(4)
The shell specifies the parameter name to pass the parameter
惊掉你下巴,程序员编码竟然可以被 996 指数化
【kali-密码攻击】(5.2.1)密码分析:Hash Identifier(哈希识别)
How to add control panel to right click menu in win7
【报错】ModuleNotFoundError: No module named ‘scp‘
破产企业的职工退休怎么办?
DP 优化方法合集
365 days challenge LeetCode1000 questions - Day 052 Step by step summation to get the minimum value of positive numbers Greedy
Unity image使用长图后 图片很糊
基于Web的疫情隔离区订餐系统