Java递归插入排序？

发布时间：2020-12-15 05:19:57 所属栏目：Java 来源：网络整理

导读：所以我试图将下面的代码变成一个递归方法,插入排序,但是尽管我尝试的却不能.谁能帮我？ 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] = ar

所以我试图将下面的代码变成一个递归方法,插入排序,但是尽管我尝试的却不能.谁能帮我？

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

解决方法

试试这个：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!