📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1549| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
wszxy | 只看该作者 |倒序浏览
全局:

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

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

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


想了半天想不出来 求大佬解答 会加米
-baidu 1point3acres


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

merge sort.png (196.62 KB, 下载次数: 1)

merge sort.png

上一篇:34岁本科毕业想转CS或者DS,求建议
下一篇:EE博后-转码咨询
全局:
本帖最后由 idealmaster 于 2021-11-21 11:12 编辑
. 1point 3 acres
普林斯顿算法课有讲过相关优化: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 | 只看该作者
全局:
xindubawukong 发表于 2021-11-21 10:54
感觉答主对递归理解不够深入,我也不知道咋解释了

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

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

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

使用道具 举报

推荐
 楼主| wszxy 2021-11-22 01:43:43 | 只看该作者
全局:
Odyssessydo 发表于 2021-11-21 11:29
只把return nums改成return temp是可以的

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

使用道具 举报

🔗
 楼主| wszxy 2021-11-22 00:33:55 | 只看该作者
全局:
自顶一下
回复

使用道具 举报

全局:
帮顶一下,友情支援
回复

使用道具 举报

全局:
感觉答主对递归理解不够深入,我也不知道咋解释了

这个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 | 只看该作者
全局:
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序,因此temp就不会有序。

评分

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

查看全部评分

回复

使用道具 举报

全局:
只把return nums改成return temp是可以的

评分

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

查看全部评分

回复

使用道具 举报

🔗
 楼主| wszxy 2021-11-22 01:44:37 | 只看该作者
全局:
fropen 发表于 2021-11-21 11:26
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序, ...

啊 一语点醒梦中人 !!. From 1point 3acres bbs
太感谢了!!
回复

使用道具 举报

🔗
 楼主| wszxy 2021-11-22 01:45:24 | 只看该作者
全局:
fropen 发表于 2021-11-21 11:26
temp里面[s,e]的有序依赖于nums里面[s,mid],[mid,e]的有序。如果你不拷贝回去,nums里面子数组就不会有序, ...

大佬 明天给宁加米
回复

使用道具 举报

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

本版积分规则

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