java - Java 程序 - 使用 For 循环的插入排序

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 循环的每次迭代后使用

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 集合有自己的排序方法，速度更快。