查看: 588|回复: 12
收起左侧

[转CS-自学] 求问一个关于merge sort的问题 (会加米)

|只看干货
wszxy | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
想请教一个问题 就是下图片这个merge sort一个 array 时,为啥要最后 把temp里的内容再倒回 nums里面呢?? 我把这步删了 然后 return temp 结果就不正确,可是 temp里面不都已经是正确答案了??为啥一定要return nums呢??


想了半天想不出来 求大佬解答 会加米



补充内容 (2021-11-22 01:55 +8:00):
感谢各位的解答
我弄懂来
由于加米限制,会一一加米的
merge sort.png

上一篇:34岁本科毕业想转CS或者DS,求建议
下一篇:EE博后-转码咨询
idealmaster 2021-11-22 02:31:12 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (1302)
 
 
3% (41)    👎
本帖最后由 idealmaster 于 2021-11-21 11:12 编辑

普林斯顿算法课有讲过相关优化:https://algs4.cs.princeton.edu/lectures/keynote/22Mergesort.pdf,第21页,其实只要在递归里互换nums和temp,就不再需要每次都把temp里排好序的数贴回nums里。
首先初始化temp不再是个空数列,而是复制nums,其次在递归里把mergesort(nums, left, right, temp)那两行改成mergesort(temp, left, right, nums)即可。
这样一来每次merge还是在temp里实现排序合并,但那个temp其实是parent call里的nums
回复

使用道具 举报

 楼主| wszxy 2021-11-22 01:31:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎
xindubawukong 发表于 2021-11-21 10:54
感觉答主对递归理解不够深入,我也不知道咋解释了

这个mergesort函数就是将num数组的l到r排好序,但利用一 ...

emmm 可是我发现 如果 不删除
for(int i = start; i<= end;i++){
           nums=temp; }
返回 temp 结果也是正确

如果删除这个for循环 返回 temp 结果就是没merge的结果,这个for循环 除了 把 temp中的内容 倒到 nums里 还有什么别的用吗?
回复

使用道具 举报

 楼主| wszxy 2021-11-22 01:43:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎
Odyssessydo 发表于 2021-11-21 11:29
只把return nums改成return temp是可以的

对 我发现了
但是 为啥还需要 for(int i = start; i<= end;i++){. 1point3acres
           nums=temp; } 这个for循环呢 ?
这个for循环 除了把temp结果倒回nums 还有别的用吗?
我把这个for循环删掉 返回 temp 就不对
回复

使用道具 举报

 楼主| wszxy 2021-11-22 00:33:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎
自顶一下
回复

使用道具 举报

superhuman 2021-11-22 00:46:07 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
帮顶一下,友情支援
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎
感觉答主对递归理解不够深入,我也不知道咋解释了

这个mergesort函数就是将num数组的l到r排好序,但利用一个temp数组作为临时数组。所以在merge两边的时候,也是用从num数组里取出两边的数进行归并,只不过临时保存在temp数组里,最后还是要copy到num里。这样mergesort返回时,才能保证num数组的l到r是有序的。

补充内容 (2021-11-22 00:55 +08:00):
l和r就是start和end
回复

使用道具 举报

fropen 2021-11-22 01:26:55 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (65)
 
 
0% (0)    👎
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序,因此temp就不会有序。

评分

参与人数 1大米 +1 收起 理由
wszxy + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

Odyssessydo 2021-11-22 01:29:21 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
只把return nums改成return temp是可以的

评分

参与人数 1大米 +1 收起 理由
wszxy + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

 楼主| wszxy 2021-11-22 01:44:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎
fropen 发表于 2021-11-21 11:26
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序, ...

啊 一语点醒梦中人 !!
太感谢了!!
回复

使用道具 举报

 楼主| wszxy 2021-11-22 01:45:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (1006)
 
 
16% (196)    👎
fropen 发表于 2021-11-21 11:26
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序, ...

大佬 明天给宁加米
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表