在此mergesort实现中每次都调用merge



在下面的代码中,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一次。

最新更新