-1

if (low < high) {以下のコードでは、mergesortメソッドの条件内で毎回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++;
            }

          }
}
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ただし、再帰が終了するときを除いて、はい、メソッドへの呼び出しごとに1回マージが呼び出されます。

于 2013-02-26T21:56:01.293 に答える