RoyNewDawn 2019-06-23 15:53 采纳率: 8.3%
浏览 812

如何理解归并排序中的递归使得两个有序数组有序再按比较首元素合并?

void mergesort(int arr[],int lo,int hi) {
    int mid = (lo+hi) >> 1;
    if (lo<hi){
    mergesort(arr,lo, mid);
    mergesort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
    }
}

搞不懂mergesort(arr,lo,mid)怎么就让左边的元素有序了?
我的一些理解是,mergesort这个递归函数的出路是lo==hi,每一次调用自身,相当于把mid
不断除以2,按照这样,我们第一个递归调用应该得到一个元素的区间(假设
lo==0)[0,)这是数组首元素。然后再去执行 mergesort(arr,lo, mid),又得到一个
元素的区间。再去执行merge(arr, lo, mid, hi),然后进行两个元素的比较,排序。
我感觉我这样的理解显然是错误的,我一直弄不懂一个递归函数的下面的执行语句究竟是怎么执行的。比如我假设有一个全局变量i放到了第一个mergesort下面,让它进行自加,究竟什么时候才会i++一次呢?i会等于几?

  • 写回答

1条回答 默认 最新

  • Italink 2019-06-26 02:27
    关注

    归并排序的解空间就是一个二叉树,递归求解过程就像是一个深度优先搜索算法,你要了解递归函数的堆栈过程

    按树结构来思考,mergesort就像是创建一个结点,如果这个结点中(lo<hi),那么就会创建两个子结点,就这样一直创建下去,就会得到一颗二叉树。
    mergesort(arr,lo, mid);
    mergesort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);

    你不觉得这样的写法就像树的先序遍历吗?

    至于你说i加了几次,显而易见,有多少个结点(mergesort函数)就加多少次

    评论

报告相同问题?

悬赏问题

  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致
  • ¥15 禅道二次开发编辑版本,上传不了发行包