-1

在下面的代码中，每次在合并排序方法中的条件内都会调用合并if (low < high) {？我认为它每次都被称为递归合并排序方法的一部分？

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

          }
}
4

2 回答 2

1 
                           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，我都会对示例进行编号，以便您更好地了解调用的时间。

于 2013-02-26T22:15:42.300 回答
0

条件

if (low < high)

是终止条件。当达到该条件时（例如，当 high = low 时），该方法将简单地返回，而不是继续进行任何递归调用。

但是，除了递归终止时，是的，每次调用该mergesort方法时都会调用一次合并。

于 2013-02-26T21:56:01.293 回答