我理解合并排序的合并部分是如何工作的,但是,由于某种原因,我无法理解调用合并函数之前发生的递归/除法部分。使用下面的示例代码,我尝试跟踪不同变量的值,但无法完全理解发生了什么。
public 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);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
对我来说,m 似乎一直被传递到 sort 中,直到它变成 0,所以看起来第二个 sort() 调用和 merge() 调用永远不会执行。有人可以解释一下所采取的步骤吗?
最佳答案
采用以下数组:
[4][2][5][1][3]
我们将把它分成两半:
[4][2][5] [1][3]
再说一遍:
[4][2] [5] [1] [3]
再说一遍:
[4] [2] [5] [1] [3]
注意我们现在有 5 个排序数组(每个数组的长度为 1)。现在是时候将它们合并在一起并进行排序了。将两个排序数组合并到一个新的排序数组中是一个非常简单的(读取:低时间复杂度)操作:
[2][4] [1][5] [3]
现在我们有 3 个排序数组。让我们再次合并它们:
[1][2][4][5] [3]
最后一次:
[1][2][3][4][5]
现已排序。
关于java - 理解Java合并排序的排序部分,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60104418/