因此,我试图理解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
)算法跳回数组的另一边并对其排序。
1条答案
按热度按时间sq1bmfud1#
在递归的某个时刻,sort(…)什么都不做,只返回(因为l==r),2个sort(…)方法就完成了。在那之后,合并就开始了,它只是将两个元素按正确的顺序排列。发生这种情况之后,上一次调用中的其他排序(…)方法就完成了,依此类推。