Почему "int mid = (left - right) / 2 + right" вызовет переполнение стека? - PullRequest
Новая
       6

Почему "int mid = (left - right) / 2 + right" вызовет переполнение стека?

0 голосов
/ 16 января 2019

Сегодня я написал код сортировки слиянием, и я сталкиваюсь с ошибкой StackOverFlow при запуске int mid = (left - right)/2 + right;. Но когда я использую int mid = left + (right - left) / 2; все нормально. Я очень смущен, потому что математическое значение двух из них одинаково (если это не так, почему?).

Я видел этот вопрос, но я не уверен, что он отвечает на эту проблему. почему left + (right-left) / 2 не переполнится?

Вот мой код ， Извините, что раньше не загружал код. 

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] array = {3,5,1,2,4,8};
        int[] result = mergeSort(array);
        System.out.println(Arrays.toString(result));
    }

    public static int[] mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int[] helper = new int[array.length];
        sort(array, helper, 0, array.length - 1);
        return array;
    }

    public static void sort(int[] array, int[] helper, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left - right)/2 + right;
        //int mid = left + (right - left) / 2;
        sort(array, helper, left, mid);
        sort(array, helper, mid + 1, right);

        combine(array, helper, left, mid, right);
    }

    public static void combine(int[] array, int[] helper, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            helper[i] = array[i];
        }

        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (helper[leftIndex] <= helper[rightIndex]) {
                array[left] = helper[leftIndex];
                left++;
                leftIndex++;
            } else {
                array[left] = helper[rightIndex];
                left++;
                rightIndex++;
            }
        }

        while (leftIndex <= mid) {
            array[left] = helper[leftIndex];
            left++;
            leftIndex++;
        }
    }
}

1 Ответ

0 голосов
/ 16 января 2019

Когда вы запустите это, рано или поздно, вероятно, left будет на единицу меньше right - например, возможно left = 3 и right = 4.

В этом случае (left - right) / 2 и (right - left) / 2 оба оцениваются как 0, поскольку целочисленное деление округляется до нуля. Итак, если у вас есть 

int mid = (left - right)/2 + right;
sort(array, helper, left, mid);

в пределах вашего звонка на sort(array, helper, left, right), тогда вы повторяете звонок с точно такими же значениями. Это вызывает бесконечную рекурсию - a StackOverflowError.

Но когда у вас есть 

int mid = left + (right - left)/2;
sort(array, helper, left, mid);

затем вы повторяете вызов с другими значениями, поэтому у рекурсии есть шанс завершиться.

...