Java: Почему мой метод рекурсивной сортировки не работает? - PullRequest
Новая
       62

Java: Почему мой метод рекурсивной сортировки не работает?

0 голосов
/ 12 марта 2019

Метод рекурсивной сортировки, который я написал ниже, печатает адрес ("[I @ 7852e922") при использовании типичного sout, я полагаю, что это связано с моими возвращениями в sort (). Я пытался сделать метод недействительным, но это, похоже, не работает, потому что мне нужно удалить возвращаемые данные. Однако, когда я наконец заменяю его этим беспорядком, он распечатывает массив без сортировки, поэтому мой метод оказывается неэффективным: 

System.out.println(Arrays.toString(sort(array2, array2.length-1)));

Пожалуйста, будьте спокойны со мной, потому что я серьезно боролся за программирование / рекурсию из-за плохой подготовки в моих предпосылках и выучил типичный пузырь за 10 минут до написания этого. Вот вся моя тестовая программа:

TL; DR: Что не так с моим методом сортировки и как его распечатать? 

public static void main(String[] args) {
    int array2[] = new int[]{1, 3, 5, 2, 4};
    System.out.println(Arrays.toString(sort(array2, array2.length-1)));
}

    static public int[] sort(int[] array, int n) {
    int i = array[n];
    int j = i-1;
    int temp;
    if(n == 0) {
        return array;
    } else if(i < j) {
        temp = i;
        i = j;
        j = temp;
        return sort(array, n - 1);
    } else {
        return sort(array, n - 1);
    }
}

Спасибо!

РЕДАКТИРОВАТЬ: После обратной связи, это то, что мне осталось. Тест работает отлично, распечатывает мой отсортированный массив. Я обнаружил, что, глядя на код слишком долго, я склонен путать i с x [i]. Тем не менее, у меня все еще есть проблемы, избегая использования Arrays.toString () или переходя на void sort (). Я буду придерживаться этого, если придется. Сказав это, я ценю любую дальнейшую помощь. 

public static void main(String[] args) {
    int array2[] = new int[]{1, 3, 5, 2, 4};
    System.out.println(Arrays.toString(sort(array2, array2.length - 1)));
}

static public int[] sort(int[] array, int lastIndex) {
    int j = lastIndex - 1;
    int temp;
    if (lastIndex == 0) {
        return array;
    } else if (array[lastIndex] < array[j]) {
        temp = array[lastIndex];
        array[lastIndex] = array[j];
        array[j] = temp;
        return sort(array, lastIndex - 1);
    } else if (array[lastIndex] > array[j]) {
        return sort(array, lastIndex - 1);
    }
    return array;
}

Ответы [ 3 ]

0 голосов
/ 12 марта 2019

Вот ваш ответ. У меня есть комментарии в коде. Надеюсь, это поможет. 

    private static int[] sort(int[] array, int lastIndex) {
    if(lastIndex<1) { //If array has only 1 element to be sorted then return array as is.
        return array;
    }
    //move the largest number in the array to the last index of the array;
    for(int i=0;i<array.length-1;i++) {
        if(array[i] > array[i+1]) {
            //swap
            int temp = array[i];
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }
    // now we know lastIndex element is highest, sort other elements by decrementing lastIndex
    return sort(array, lastIndex-1);
}
0 голосов
/ 12 марта 2019

У вас здесь много проблем. Сначала вы сравниваете индексы (i и j - индексы, они сообщают вам положение члена в массиве). Вы решаете это, сравнивая мои значения следующим образом: 

else if(array[j] < array[i]){
     temp = array[i];
     array[i] = array[j];
     array[j] = temp;   }

Во-вторых, при такой записи будет выполняться только одна итерация пузырьковой сортировки, поэтому вы можете быть уверены, что самое низкое значение будет найдено в начале массива (если вы знаете, как работает пузырьковая сортировка). Чтобы решить эту проблему, вы должны добавить еще один слой рекурсивных вызовов, но на этот раз вы вызываете только n - 1 элементов массива, потому что наверняка отсортировали самое низкое значение.

Другой способ решить эту проблему без изменений в вашем методе сортировки - вызвать цикл for и выполнить метод сортировки n раз.

0 голосов
/ 12 марта 2019

Твой код распечатывается нормально для меня, хотя твой код неверен.

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

Проверьте https://www.geeksforgeeks.org/recursive-bubble-sort/ для рабочего рекурсивного примера.

...