Java: реализация сортировки слиянием - PullRequest
Новая
       7

Java: реализация сортировки слиянием

0 голосов
/ 17 мая 2018

Я хочу реализовать сортировку слиянием, используя один метод mergeSort, который разбивает последовательности массива int до одного элемента, и используя метод слияния для их объединения. С моим кодом, как он есть, я получаю ошибку Stackoverflow. У кого-нибудь есть идея, почему? 

public static int[] mergeSort(int[] seq) {
    return mergeSort(seq, 0, seq.length - 1);
}
private static int[] mergeSort(int[] seq, int l, int r) {

    if (seq.length < 2) {
        return seq;
    }
    int s = (l + r) / 2;
    int[] a = new int[s];
    int[] b = new int[seq.length - s];
    for (int i : a) {
        a[i] = seq[i];
    }
    for (int j : b) {
        b[j] = seq[s + j];
    }
    mergeSort(a);
    mergeSort(b);

    return merge(a, b);
}

public static int[] merge(int[] ls, int[] rs) {
    // Store the result in this array
    int[] result = new int[ls.length + rs.length];

    int i, l, r;
    i = l = r = 0;
    while (i < result.length) {
        if (l < ls.length && r < rs.length) {
            if (ls[l] < rs[r]) {
                result[i] = ls[l];
                ++i;
                ++l;
            } else {
                result[i] = rs[r];
                ++i;
                ++r;
            }
        } else if (l >= ls.length) {
            while (r < rs.length) {
                result[i] = rs[r];
                ++i;
                ++r;
            }
        } else if (r >= rs.length) {
            while (l < ls.length) {
                result[i] = ls[l];
                ++i;
                ++l;
            }
        }
    }
    return result;
}

Ответы [ 2 ]

0 голосов
/ 17 мая 2018

Есть две небольшие проблемы с вашим кодом.

Первый здесь: 

public static int[] mergeSort(int[] seq) {
    return mergeSort(seq, 0, seq.length - 1);
}

Вам нужно назвать его как return mergeSort(seq, 0, seq.length);

Причина в том, что, например, когда у вас есть 2 элемента и вы называете это так с -1, вы передаете массив с 2 элементами, но s = 1 + 0/2 = 0, и вы на самом деле не разделяете его , Каждый последующий вызов рекурсии выполняется с одним пустым массивом и одним массивом с теми же двумя элементами, что вызывает бесконечный цикл и исключение stackoverflow

Вторая проблема: 

  for (int i : a) {  and   for (int i : b) {

Вы не можете выполнять цикл for как, потому что вы хотите выполнять итерации по индексам, а не по значениям массива. Вам нужно изменить его на: 

   for (int i=0;i<a.length;i++) {
        a[i] = seq[i];
    }
    for (int i=0;i<b.length;i++) {
        b[i] = seq[s + i];
    }

И последняя проблема с вашим кодом состоит в том, что вы не присваиваете значения результирующего отсортированного массива, и когда вы делаете рекурсивные вызовы, он возвращает отсортированную подчасть, но вы не получаете результат. Это должно стать: 

a=mergeSort(a);
b=mergeSort(b);

А вот и окончательный код: 

public static void main(String... args) {
        int[] array={3,9,4,5,1} ;
        array=mergeSort(array);
        for(int i:array) {
            System.out.print(i+",");    
        }
    }


    private static int[] mergeSort(int[] seq) {

        if (seq.length < 2) {
            return seq;
        }
        int s = seq.length / 2; //You always use that value. no need for 2 methods
        int[] a = new int[s];
        int[] b = new int[seq.length - s];
        for (int i=0;i<a.length;i++) {
            a[i] = seq[i];
        }
        for (int i=0;i<b.length;i++) {
            b[i] = seq[s + i];
        }
        a=mergeSort(a);
        b=mergeSort(b);

        return merge(a, b);
    }

    public static int[] merge(int[] ls, int[] rs) {
        // Store the result in this array
        int[] result = new int[ls.length + rs.length];

        int i, l, r;
        i = l = r = 0;
        while (i < result.length) {
            if (l < ls.length && r < rs.length) {
                if (ls[l] < rs[r]) {
                    result[i] = ls[l];
                    ++i;
                    ++l;
                } else {
                    result[i] = rs[r];
                    ++i;
                    ++r;
                }
            } else if (l >= ls.length) {
                while (r < rs.length) {
                    result[i] = rs[r];
                    ++i;
                    ++r;
                }
            } else if (r >= rs.length) {
                while (l < ls.length) {
                    result[i] = ls[l];
                    ++i;
                    ++l;
                }
            }
        }
        return result;
    }
0 голосов
/ 17 мая 2018

Переполнение стека вызвано рекурсивным вызовом метода слишком много раз, возможно, бесконечным.

private static int[] mergeSort(int[] seq, int l, int r) это всегда будет вызываться с l = 0 и r = seq.length-1, так что это недействительно необходимо перегрузить.

Здесь: int s = (l + r) / 2;, если массив имеет 2 элемента, это вернет 0 (l = 0, r = 1), поэтому массив будет разделен на длину 0, идлина 2 (и вот что вызывает бесконечные рекурсивные вызовы).Добавьте один к результату, и разбиение массива будет работать правильно.

Чтобы скопировать части исходного массива, проще использовать Arrays.copyOfRange (), чем писать свой собственный цикл for.И вы пытаетесь использовать существующие элементы массивов a и b, которые все будут равны 0, для индексации.

...