Java插入排序

Question

下面是main方法调用insertionSort方法，放入多个不同大小的数组。在本例中，我只有一个数组，但将运行多个数组。我想不出如何让arr2像插入排序那样排序。从arr2的末尾往上推，直到它到达arr2中的正确位置，然后再次查看未排序的数组，将下一个数字放在arr2的末尾，然后一次又一次地排序，直到有一个排序的array.If，这将是非常好的。是的，我已经查看了其他代码，但都没有帮助我解决我的问题，我花了一周的时间试图解决这个问题。

static void insertionSort(int[] arr) {
    final long startTime = System.nanoTime(); // starts timer
    System.out.println("Insertion Sort");
    //************** Code For Sorting *****************//
    int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array
    Arrays.sort(sorted); // sorts unsorted array for comparison later on
    
    int[] arr2 = new int[arr.length];
    for(int h = 0; h < arr.length - 1; h++){// makes arr2 all 0's
        arr2[h] = 0;
    }
        
    arr2[arr2.length - 1] = arr[0];
    for(int k = 0; k < arr.length; k++){
        System.out.print(arr2[k] + ", ");
    }
    System.out.println();
    
    while(arr2 != sorted) {
        for(int i = 1; i < arr2.length; i++) {
            if(arr[i] < arr2[arr2.length-1]) {
                int last = arr2[arr2.length-1];
                int before = arr[i];
                arr2[arr2.length-1]= before;
                arr2[arr2.length-2]= last;
                
                // CANT FIGURE OUT HOW TO SORT CORRECTLY
            }

            for(int k = 0; k < arr.length; k++) {
                System.out.print(arr2[k] + ", ");
            }

            System.out.println();
        }
    }

    for(int k = 0; k < arr.length; k++) {
        System.out.print(arr2[k] + ", ");
    }
}

public static void main(String[] args) {  
    int arr[] = {}; // Array that will be put into each sort method
    //****************Multiple Arrays for testing*******************//
    
    /* ************All Arrays Are Whole Numbers 1-100***************
    arr1 = Array of size 20
***************************************************************  */
    int arr1[] = {6,3,20,10,11,2,9,1,19,17,4,16,8,15,18,14,5,7,12,13}; // {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
//**************************************************************//
    int arrayNumber = 1;
    while(arrayNumber < 2){
        if (arrayNumber == 1){
            arr = arr1;
        }
System.out.println("Array "+ arrayNumber +" Before Sorting");
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
        System.out.println();
        //************* Array put into Methods***************//
 insertionSort(arr);
//***************************************************//
        arrayNumber++; // Adds 1 to arrayNumber to show next array
    }

}

Answer 1

首先，arr2永远不能== sorted。==意味着两个对象在memory.and中具有相同的地址。然后，插入排序是对一组对象进行排序，并将它们存储在一个排序的集合中，在您的insertionSort(int[] arr)方法中，至少需要两个数组，您的arr2是一个排序的array.but，您需要更多的空间，换句话说，您可以初始化arr2 = new int[arr.length*2];.and，然后只需迭代arr .and插入arr[i]到正确的place.the中。正确的地方是当您将arr[i]与D9进行比较时，索引j是正确的位置，然后在索引j和arr2的最后一个元素之间移动arr2的所有元素，我们说的是arr[k]，而不是arr2.length-1，重要的是，你应该先移动arr2[k]一步，就像arr[k+1]=arr[k];一样，从现在开始，一个对象被插入到arr2中。