插入排序

关键点：每次将一个待排序的元素与已排序的元素进行逐一比较，直到找到合适的位置按大小插入。

image.png

        public void  insert(int[] arr){
        print_a(arr);
        for(int i = 1;i < arr.length; i++){
            if(arr[i] < arr[i-1]){//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
                int temp = arr[i];
                int j;
                System.out.println("temp =  "+temp);
                for(j = i-1; j >= 0 && temp < arr[j] ; j--){
                    System.out.println("======================start");
                    System.out.println("arr[j] =  "+arr[j]);
                    System.out.println("temp =  "+temp);
                    print_a(arr);
                    System.out.println("arr[i] ===="+arr[i]+" i===="+i);
                    System.out.println("i-1="+(i-1)+"    j="+j);
                    arr[j+1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置
                    System.out.println("======================end");
                }
                arr[j+1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
            }
        }
    }

    public void print_a(int[] a){
        for (int s:a) {
            System.out.print(s+" ");
        }
        System.out.println();
    }

    @Test
    public  void test_insert() {
        int[] a ={4,2,1,5};
        insert(a);
    }

输出结果如下：自己可以一步步分析

image.png