#java #sorting #recursion #insertion-sort
#java #сортировка #рекурсия #вставка-сортировка
Вопрос:
Итак, я пытаюсь преобразовать следующий код в рекурсивный метод insertion sort, но, как бы я ни старался, у меня не получается. Кто-нибудь может мне помочь?
public static void insertionSort(int[] array){
for (int i = 1; i < array.length; i ){
int j = i;
int B = array[i];
while ((j > 0) amp;amp; (array[j-1] > B)){
array[j] = array[j-1];
j--;
}
array[j] = B;
}
}
Редактировать:
Я думал о чем-то подобном, но мне это не кажется очень рекурсивным…
public static void insertionSort(int[] array, int index){
if(index < array.length){
int j = index;
int B = array[index];
while ((j > 0) amp;amp; (array[j-1] > B)){
array[j] = array[j-1];
j--;
}
array[j] = B;
insertionSort(array, index 1);
}
}
Комментарии:
1. Шаг 1: Используйте читаемое форматирование
2. Вам нужно будет быть более конкретным. Что вы хотите, чтобы ваша рекурсия выполняла?
3. Я хочу, чтобы метод был рекурсивным. Вызывать себя внутри метода и затем иметь базовое условие, которое остановило бы его от вызова самого себя навсегда.
4. «как бы я ни старался, я не могу» < — Не могли бы вы отредактировать свой вопрос, чтобы показать методы, которые вы пробовали, даже если это псевдокод.
5. Ну, я думал убрать цикл for и вместо этого сделать его рекурсивным, снова вызвав метод с другими данными внутри, но я запутываюсь, когда пытаюсь это сделать.
Ответ №1:
Попробуйте это:
public class RecursiveInsertionSort {
static int[] arr = {5, 2, 4, 6, 1, 3};
int maxIndex = arr.length;
public static void main(String[] args) {
print(arr);
new RecursiveInsertionSort().sort(arr.length);
}
/*
The sorting function uses 'index' instead of 'copying the array' in each
recursive call to conserve memory and improve efficiency.
*/
private int sort(int maxIndex) {
if (maxIndex <= 1) {
// at this point maxIndex points to the second element in the array.
return maxIndex;
}
maxIndex = sort(maxIndex - 1); // recursive call
// save a copy of the value in variable 'key'.
// This value will be placed in the correct position
// after the while loop below ends.
int key = arr[maxIndex];
int i = maxIndex - 1;
// compare value in 'key' with all the elements in array
// that come before the element key.
while ((i >= 0) amp;amp; (arr[i] > key)) {
arr[i 1] = arr[i];
i--;
}
arr[i 1] = key;
print(arr);
return maxIndex 1;
}
// code to print the array on the console.
private static void print(int[] arr) {
System.out.println();
for (int i : arr) {
System.out.print(i ", ");
}
}
}
Комментарии:
1. Описание ответа отсутствует.
2. Добавьте описание и комментарий, чтобы объяснить свой ответ.
3. @Varun: Добро пожаловать в SO, попробуйте добавить некоторые пояснения к своим ответам, наличие некоторых комментариев в коде также будет полезно другим для быстрого понимания / улучшения.
4. Извините за это… Я надеюсь, что это поможет, дайте мне знать, если потребуется что-то еще.
Ответ №2:
public static void insertionSort(int[] array, int index) {
if(array.length == index 1) return;
insertionSort(array, index 1);
// insert array[index] into the array
}
Ответ №3:
Вы можете попробовать этот код. Это работает правильно.
public static int[] InsertionSort(int[] dizi, int n)
{
int i;
if (n < 1) {
InsertionSort(dizi, n - 1);
}
else {
int key = dizi[n];
i = n - 1;
while (i >= 0 amp;amp; dizi[i] > key) {
dizi[i 1] = dizi[i];
i = i - 1;
}
dizi[i 1] = key;
}
return dizi;
}
Комментарии:
1. На самом деле это работает некорректно. И когда вы отвечаете, лучше всего отвечать с пояснениями.
Ответ №4:
для алгоритма рекурсии мы начинаем со всего массива A[1..n], сортируем A[1..n-1], а затем вставляем A[n] в правильную позицию.
public int[] insertionSort(int[] array)
{
//base case
if(array.length==1) return new int[]{ array[0] };
//get array[0..n-1] and sort it
int[] arrayToSort = new int[array.length - 1]{ };
System.arraycopy(array, 0, arrayToSort, 0, array.length -1);
int[] B = insertionSort(arrayToSort);
//now, insert array[n] into its correct position
int[] C = merge(B, array[array.length - 1]);
return C;
}
private int[] merge(int[] array, int n)
{
int[] arrayToReturn = new int[array.length 1] {};
int j = array.length-1;
while(j>=0 amp;amp; n <= array[j])
{
arrayToReturn[j 1]=array[j;
j--;
}
arrayToReturn[j] =
}
Ответ №5:
Попробуйте приведенный ниже код, предоставив ele в виде массива целых чисел sortedIndex = индекс первого элемента и index = индекс второго элемента:
public static void insertionSort(int[] ele, int sortedIndex, int index) {
if (sortedIndex < ele.length) {
if (index < ele.length) {
if (ele[sortedIndex] > ele[index]) {
ele[sortedIndex] = ele[index];
ele[index] = ele[sortedIndex] - ele[index];
ele[sortedIndex] = ele[sortedIndex] - ele[index];
}
insertionSort(ele, sortedIndex, index 1);
return;
}
if (index == ele.length) {
sortedIndex ;
}
insertionSort(ele, sortedIndex, sortedIndex 1);
}
}
Ответ №6:
public static void sort(int[] A, int p, int r) {
if (p < r) {
int q = r - 1;
sort(A, p, q);
combine(A, p, q, r);
}
}
private static void combine(int[] A, int p, int q, int r) {
int i = q - p;
int val = A[r];
while (i >= 0 amp;amp; val < A[p i]) {
A[p i 1] = A[p i];
A[p i] = val;
i--;
}
}
public static void main(String... strings) {
int[] A = { 2, 5, 3, 1, 7 };
sort(A, 0, A.length - 1);
Arrays.stream(A).sequential().forEach(i -> System.out.print(i ", "));
}
Ответ №7:
public class test
{
public static void main(String[] args){
test h = new test();
int a[] = { 5, 8, 9, 13, 65, 74, 25, 44, 67, 2, 1 };
h.ins_rec(a, a.length-1);
for(int i=0; i<a.length; i )
log(a[i]);
}
void ins_rec(int a[], int j){
if( j == 0 ) return;
ins_rec(a, j - 1);
int key = a[ j ];
sort(a, key, j - 1);
}
void sort(int a[], int key, int i){
if( (i < 0) || (a[i] < key) ) {
a[ i 1 ] = key;
return;
}
a[ i 1 ] = a[ i ];
sort(a, key, i - 1);
}
private static void log(int aMessage){
System.out.println("tt" aMessage);
}
}