Java рекурсивная вставка сортировки?

Question

Итак, я пытаюсь превратить следующий код в рекурсивный метод сортировки вставкой, но столько, сколько я пытаюсь, я не могу. Кто-нибудь может мне помочь?

public static void insertionSort(int[] array){
    for (int i = 1; i < array.length; i++){
        int j = i;
        int B = array[i];
        while ((j > 0) && (array[j-1] > B)){
            array[j] = array[j-1];
            j--;
        }
        array[j] = B;
    }
}

EDIT: Я думал о чем-то вроде этого, но это не выглядит для меня рекурсивно ...

public static void insertionSort(int[] array, int index){
    if(index < array.length){
        int j = index;
        int B = array[index];
        while ((j > 0) && (array[j-1] > B)){
            array[j] = array[j-1];
            j--;
        }
        array[j] = B;
        insertionSort(array, index + 1);
    }
}

Answer 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) && (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 + ", ");
        }
    }
}

Answer 2

Вы можете попробовать этот код. Работает правильно.

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 && dizi[i] > key) {
            dizi[i + 1] = dizi[i];
            i = i - 1;
        }

        dizi[i + 1] = key;
    }

    return dizi;
}

Answer 3

public static void insertionSort(int[] array, int index) {
    if(array.length == index + 1) return;

    insertionSort(array, index + 1);

    // insert array[index] into the array

}

Answer 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 && n <= array[j])
   {
      arrayToReturn[j+1]=array[j;
      j--;
   }

   arrayToReturn[j] = 
}

Answer 5

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 && 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 + ", "));
}

Answer 6

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("\t\t"+aMessage);
  }
}

Answer 7

Попробуйте приведенный ниже код, указав 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);
    }
}