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语句放入其中，并观察到在低>=高之后仍在执行。在这里，这些调用被跳过了。

        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);
     }

Answer 2

对于自上而下的合并排序，直到数组的递归拆分产生大小为1的两次运行，才会发生合并。这将是mergesort()调用merge()的第一个实例。然后，mergesort()的实例返回到mergesort()的前一个实例，最终到达对merge()的调用，依此类推。合并顺序为深度优先/左侧优先。

相比之下，自底向上合并排序(大多数库使用自底向上合并排序的某种变体，如timsort)，跳过递归并将n个元素的数组视为大小为1的n次运行，并立即开始合并运行。运行的索引是迭代生成的(通过循环)。

这是一个自上而下合并排序的操作顺序示例，即深度优先，左先。竖线表示当前数组的左半部分和右半部分之间的分割。

|4 2 8 6 0 5 1 7 3 9|
|4 2 8 6 0|5 1 7 3 9|
|4 2|8 6 0|
|4|2|
|2 4|
    |8|6 0|
      |6|0|
      |0 6|
    |0 6 8|
|0 2 4 6 8|
          |5 1|7 3 9|
          |5|1|
          |1 5|
              |7|3 9|
                |3|9|
                |3 9|
              |3 7 9|
          |1 3 5 7 9|
|0 1 2 3 4 5 6 7 8 9|

Answer 3

实际情况是，每个堆叠的方法调用都会被执行。如果您以图形方式表示堆栈，则在每个步骤中都有以下内容：

1.- bottom/top --> mergeSort(0, 5)

2.- top    --> mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

3.- top    --> mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

4.- top    --> mergeSort(0, 0) --> breaks and go back
               mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

5.- top    --> mergeSort(0, 1) --> finish and continue with next line
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

6.- top    --> mergeSort(2, 2) --> next line after mergeSort(0, 1)
               mergeSort(0, 2)
    bottom --> mergeSort(0, 5)

7.- etc.

将第一步用图形表示出来后，您就可以计算出其余的步骤。希望这能有所帮助