Как правильно реализовать пузырьковую сортировку рекурсивно?
Я пишу метод для реализации пузырьковой сортировки с рекурсией, и мой базовый случай — «длина массива», в этом случае мне нужно рекурсивно вызывать функцию от «0» до array.length-1, однако, когда я прошел через коды от других людей, я нашел их все, используя базовый случай «1», и это запускает рекурсию от array.length к «1». Я знаю, что обе наши рекурсии выполняются одинаковое количество раз и получают один и тот же результат, но я просто немного смущен, значит ли это, что мое понимание рекурсии неверно?
мой код:
public static void bubbleRecursion(int arr[],int n){
if (n==arr.length){
System.out.println(Arrays.toString(arr));
return;
}
for (int i = 0;i<arr.length-1-n;i++){
if (arr[i]>arr[i+1]){
int temp;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
bubbleRecursion(arr, n+1);
}
bubbleRecursion(array,0);
чужой код:
public static void sortingRecursion(int[] arr, int n){
if (n == 1){
return;
}
for (int i = 0;i < n-1;i++){
if (arr[i]>arr[i+1]){
int temp;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
sortingRecursion(arr, n-1);
}
sortingRecursion(array, array.length);
Затем я посмотрел определение рекурсии, кажется, что ввод должен становиться все меньше и меньше каждый раз, но мой код каждый раз увеличивает значение n, так что теперь я немного запутался, означает ли это, что мой код является неправильный ответ, хотя вывод правильный?
Кто-нибудь может мне помочь? Спасибо
Почему if (n == 1) return; вместо if (n == 0) return;?
Ответы 2
Ваш базовый случай должен быть if (n == 0) return;
Решение
public static void sortingRecursion(int[] arr, int n){
if (n == 0){
return;
}
for (int i = 0;i < n;i++){
if (arr[i]>arr[i+1]){
int temp;
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
sortingRecursion(arr, n-1);
}
Применение
int array[] = {5, 4, 7, 2, 8};
sortingRecursion(array, array.length - 1);
System.out.println(Arrays.toString(array));
Выход
[2, 4, 5, 7, 8]
Отредактировано
Базовый вариант 1 тоже работает. Массив с одним элементом (например, [42]) уже отсортирован правильно.
ввод должен становиться все меньше и меньше каждый раз, но мой код каждый раз увеличивает значение n
Это правда, но поскольку вы используете n иначе, чем в другой версии, вы все равно каждый раз уменьшаете ввод: условие цикла срабатывает раньше при каждой следующей рекурсии, поскольку array.length - 1 - n становится меньше. Так что не беспокойтесь, ваша версия также уменьшает проблему на каждом рекурсивном шаге.
просматривая коды от других людей, я обнаружил, что все они используют базовый регистр "1"
Это имеет смысл, так как в этом случае условие цикла будет ложным: i < n - 1 будет ложным, когда n равно 1.
Вы можете сделать то же самое в своей версии, изменив базовый тест на if (n==array.length-1).
Однако это не означает, что ваш текущий базовый тест ужасно неверен. Это просто означает, что когда n равно array.length-1, цикл все равно будет выполняться, но не будет повторяться, потому что условие цикла сразу становится ложным. И тогда следующий рекурсивный вызов все равно попадет в базовый случай. Так что это просто означает, что есть еще один рекурсивный вызов, который ничего не делает.
Если у вас есть массив/список размера 1, он уже отсортирован. Пустой массив/список тоже сортируется, но уже можно остановиться на 1; он не становится «более упорядоченным».