合并排序过程

cygmwpex  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(417)

因此,我试图理解mergesort算法的实现,但我无法理解进程在开始时是如何流动的,而它必须划分数组。在排序算法下面

void sort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // Sort first and second halves 
        sort(arr, l, m);          //talking about 
        sort(arr , m+1, r);       //this part 

        // Merge the sorted halves 
        merge(arr, l, m, r); 
    }

我想到的唯一一个分支数组的模型是这样的(考虑数组{48,34,4,1}):

m(a, l(0), r(3));
  m(a, l(0), m(1));
    m(a, l(0), m(0));
    m(a, m+1(1), r(1));
  m(a, m+1(2), r(3));
    m(a, l(2), m(2));
    m(a, m+1(3), r(3);

这是打电话的顺序吗?电话:

sort(arr, l, m);      
    sort(arr , m+1, r);

我也不明白为什么方法参数不满足if条件( l<r )算法跳回数组的另一边并对其排序。

sq1bmfud

sq1bmfud1#

在递归的某个时刻,sort(…)什么都不做,只返回(因为l==r),2个sort(…)方法就完成了。在那之后,合并就开始了,它只是将两个元素按正确的顺序排列。发生这种情况之后,上一次调用中的其他排序(…)方法就完成了,依此类推。

相关问题