java合并排序算法中的递归方法

I have the below merge sort code in my application. I am very confused on how the recursive method gets called again after it comes out of the if block when the if condition is not met. I debugged my code, but I am still not getting it. The sort method that calls mergesort(0, number - 1) starts first at mergesort(0, 5). low is less than high, middle is 2, so mergesort(0, 2) is run next. This goes on until we have mergesort(0, 0) in which case low is not less than high, so it comes out of the if block. But when I debug, the method returns, and it starts again after mergesort(0, 0) case. How does the call happen again? Please help me. Thank you for taking the time to read my question :)

我在我的应用程序中有以下合并排序代码。我很困惑如果在不满足if条件时if块出来之后再次调用递归方法。我调试了我的代码,但我仍然没有得到它。调用mergesort(0,number - 1)的sort方法首先在mergesort(0,5)处开始。 low低于high,middle为2,所以mergesort(0,2)接下来运行。这一直持续到我们有mergesort(0,0),在这种情况下,low不低于high,因此它来自if块。但是当我调试时,该方法返回,并在mergesort(0,0)case之后再次启动。电话如何再次发生?请帮我。感谢您抽出宝贵时间阅读我的问题:)

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

    private int number;


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

    private int[] 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;
            // 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);
        }
        return numbers;
    }

    private int[] 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++;
        }
        return numbers;

    }
}

1 个解决方案

#1

This is because the mergesort method calls itself twice. You can print out the stack to see what happens.

这是因为mergesort方法自己调用两次。您可以打印出堆栈以查看会发生什么。

For example, when call mergesort(0,1), the method will call mergesort(0,0) first and then mergesort(1,1).

例如,当调用mergesort(0,1)时,该方法将首先调用mergesort(0,0),然后调用mergesort(1,1)。

#1