当前位置:网站首页>空间复杂度为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)
边栏推荐
猜你喜欢
即时通讯开发如何撸一个WebSocket服务器
Sikuli 基于图形识别的自动化测试技术
UI遍历的初步尝试
y92.第六章 微服务、服务网格及Envoy实战 -- Envoy基础(三)
Penetration Testing and Offensive and Defense Confrontation - Vulnerability Scanning & Logic Vulnerability (Part1)
[转] Typora_Markdown_图片标题(题注)
小程序中计算距离信息
【论文笔记】基于深度学习的机器人抓取虚拟仿真实验教学系统
ASEMI整流桥GBJ1010参数,GBJ1010规格,GBJ1010封装
Fedora 36 dnf 安装ModSecurity和 OWASP 核心规则集
随机推荐
R语言使用cox函数构建生存分析回归模型、使用subgroupAnalysis进行亚组分析并可视化森林图
ABAP 里文件操作涉及到中文字符集的问题和解决方案
对修饰器的实验支持功能在将来的版本中可能更改。在 “tsconfig“ 或 “jsconfig“ 中设置 “experimentalDecorators“ 选项以删除此警告
03|Process Control
跳房子游戏
Research on Ethernet PHY Chip LAN8720A Chip
MySQL最大连接数限制如何修改
阿里云混合云管理平台多Region架构
【ROS2原理10】Interface数据的规定
Unity vertex animation
【软考软件评测师】软件测试基础知识
Aptos 深度解读:机遇、挑战与风险
CAS:183896-00-6 (Biotin-PEG3-C3-NH2) PEG derivative
OpenSSF的开源软件风险评估工具:Scorecards
DP 优化方法合集
解决sed替换文本,里面含有“/“、“#”等特殊字符的问题
Unity editor extension interface uses List
RedHat红帽RHEL7安装与使用,VMware Workstation16 Pro虚拟机的安装与使用
Xi'an biotin-tetrapolyethylene glycol-amide-4phenol light yellow semi-solid
Involved in PEG-Biotin (CAS: 1778736-18-7) Biotin-PEG4-OH is widely used in molecular target detection