java - MergeSort - 实现

Question

在多次递归调用后，low 变为等于 high，递归中断。之后会发生什么？谁能解释一下。合并过程对我来说很清楚:当调用 mergesort(0,5) 时，它会再次调用自身:mergesort(0,2) 然后是 mergesort(0 ,1)。最后 mergesort(0,0) 然后递归中断。

之后会发生什么？控件在代码中的什么位置？堆栈用在什么地方？请帮助我。

public class MergeSort {
private int[] numbers;
private int[] helper;

private int number;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
}

private void mergesort(int low, int high) {
    // check if low is smaller than 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;
        // 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 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++;
    }

}

 public static void main(String[] args){
     int arr[] = {78,9,45,7,2,90};
     new MergeSort().sort(arr);
        for(int i = 0; i < arr.length;i++){
            System.out.print(arr[i] + "\t");
        }
 }

Answer 1

您可以放置​​ else 语句并观察到在 low >= high 之后执行仍然完成。在这里，这些调用只是被跳过了。

        private void mergesort(int low, int high) { 
    // check if low is smaller than 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; // 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); }

    else 
    System.out.prinln("low is higher than high. Low is " +low+ "high is" +high);
     }