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;
    }
}

编辑:我在想这样的事情,但它对我来说看起来并不是很复杂......

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