在下面的代码中,mergesort方法中每次在条件if (low < high) {
内调用merge吗?我认为它每次都被调用,作为递归合并排序方法的一部分?
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++;
}
}
}
mergesort(1,3) (1)
/
/ (2) (5)
v v
mergesort(1,2) mergesort(2,3)
/ /
(3) / (4) (6) / (7)
mergesort(1,1) mergesort(2,2) mergesort(2,2) mergesort(3,3)
/ /
/ /
merge (8) merge (9)
_________> merge <__________/
(10)
您可以看到,每当low < high
调用merge
时,我都会对示例进行编号,这样您就可以更好地了解调用的时间。
条件
if (low < high)
是终止条件。当达到该条件时(例如,当high=low时(,方法将简单地返回,而不是继续任何递归调用。
不过,除了递归终止时,是的,每次调用mergesort
方法都会调用merge一次。