插入排序程序不能正常工作

Question

     public static void insertionSort(int[] arr) {

        // each outer loop iteration inserts arr[i] into the correct location of
        // the already-sorted sub-list: arr[0] through arr[i-1]

            for (int i = 1; i < arr.length; i++) {
                int valueToInsert = arr[i];
                int loc = 0;
                while (loc < i && arr[loc] < valueToInsert) { 
                    loc++;
                 }
                for (int j = loc; j < i; j++) { 
                    arr[j+1] = arr[j]; // some issue with this 
                                // loop as I'm overriding the next element
                }
            arr[loc] = valueToInsert; //// put the value 
                                       //in correct location in sub-list 
        } 
    }

以上是我的插入排序代码，不能正常使用，示例输入如下

input [3, 9, 2]
expected output is [2, 3, 9]
But I'm getting [2, 3, 3]

请让我更多地了解有关插入排序的问题，并请求您的快速回复

Answer 1

问题是

for (int j = loc; j < i; j++) { 
    arr[j+1] = arr[j]; 
}

数组中的前一个值将覆盖下一个。应该是

for (int j = i-1; j >= loc; j--) { 
    arr[j+1] = arr[j]; 
}

Answer 2

 public class InsertionSort {

    public static void main(String...strings){
        int[] array= {3, 9, 2};
        intsertionSort(array);
    }
    public static void intsertionSort(int[] arr){
        for (int i=1; i<arr.length;i++){
            int valueToInsert =arr[i];
            int j;
            //below this is error point in your code
            for(j=i-1;j>=0 && valueToInsert <arr[j];j--)
                arr[j+1]=arr[j];
            arr[j+1]=valueToInsert;
        }
        //used for testing the function
        for(int a:arr){
            System.out.println(a);
        }
    }
}

输入[3, 9, 2]

输出为[2, 3, 9]

这是IdeOne Link

插入排序程序不能正常工作

insertion sort program not working properly

java

arrays

insertion-sort