在这个mergesort实现中,每次都会调用java合并
在下面的代码中,每次在mergesort方法的条件if (low < high) {
内调用merge?我认为它每次都被称为递归mergesort方法的一部分
package sorting;
public class MyMergeSort extends Print{
private static int[] numbers;
private static int[] helper;
private static int number;
public static void main(String args[]){
int[] array = {1 , 3 , 5 , 7 , 8};
sort(array);
}
public static void sort(int[] values) {
numbers = values;
number = values.length;
helper = new int[number];
mergesort(0, number - 1);
}
private static void mergesort(int low, int high) {
// Check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
println("low is "+low); println("high is "+high); println("middle is "+middle);
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
private static void merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
}
# 1 楼答案
您可以看到,每当
low < high
有对merge
的调用时,我对示例进行了编号,以便您更好地理解调用的时间# 2 楼答案
情况
是终止条件。当达到该条件时(例如,当high=low),该方法将简单地返回,而不是继续进行任何递归调用
不过,除了递归终止之外,是的,对
mergesort
方法的每次调用都会调用merge一次