Java程序-用于循环的插入排序

Question

我编写了一个用于插入排序的java程序。

public class InsertionSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int arr[] = { 12, 11, 13, 5, 6 };

        int len = arr.length;

        for(int i=0;i<len-1;i++) {

            for(int j=i+1;j<len;j++) {

                if(arr[j] < arr[i]) {
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        for(int i=0;i<len;i++) {
            System.out.print(arr[i]+ " ");
        }

    }

}

请您告诉我，如果上面的程序是正确的，是正确的方式进行插入排序。我得到了正确的输出。

Answer 1

如果尝试在j循环的每一次迭代之后打印New数组，则使用

System.out.println(Arrays.toString(arr))

这将导致下面的语句，将分析作为注释//插入排序，从索引1的元素开始，因为它比较数字的左边。

和每种排序之后，当前值左侧的所有元素都将在以前的迭代中进行排序。

[11, 12, 13, 5, 6] // correct since 11 < 12
[11, 12, 13, 5, 6] //correct since 12 < 13
[5, 12, 13, 11, 6] //5 has changed its position which is correct but also Here you can //see the position of 11 changed
[5, 12, 13, 11, 6]
[5, 12, 13, 11, 6]
[5, 11, 13, 12, 6] 
[5, 6, 13, 12, 11] 
[5, 6, 12, 13, 11]
[5, 6, 11, 13, 12]
[5, 6, 11, 12, 13]

试试下面的代码

public static void main(String[] args)  {
        int arr[] = { 12, 11, 13, 5, 6 };
        int len = arr.length;
        for(int i=1; i<len; i++) {
            int key = arr[i];
            int j = i - 1;
            for ( ; (j >= 0 && arr[j] > key); j--) { 
                arr[j + 1] = arr[j];  
            } 
            arr[j + 1] = key;
            System.out.println(Arrays.toString(arr));
        }
    }

它会使你的产量低于

[11, 12, 13, 5, 6]
[11, 12, 13, 5, 6]
[5, 11, 12, 13, 6]
[5, 6, 11, 12, 13]

源https://www.geeksforgeeks.org/insertion-sort/

Answer 2

它是正确的，但它不是插入排序。你写的是泡泡。

插入排序如下所示：

public class InsertionSort {    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[] = { 12, 11, 13, 5, 6 };
        int len = arr.length;
        for(int i=0;i<len-1;i++) {
            int max_idx = i
            for(int j=i+1;j<len;j++) {
                if(arr[max_idx] < arr[j]) {
                    max_idx = j
                }
            }

            if (i != max_idx) {
                int temp = arr[max_idx];
                arr[max_idx] = arr[i];
                arr[i] = temp;
            }
        }
        for(int i=0;i<len;i++) {
            System.out.print(arr[i]+ " ");
        }
    }
}

顺便说一句，Java集合有自己的排序方法，这种方法要快得多。