数组算法：插入排序

package com.array;

import java.util.Arrays;

/**
 * @Author: liuchang
 * @CreateTime: 2020.7.12
 * @Description: 郑州工程技术学院-中德学院
 */
/*
    数组算法：直接插入排序：从1索引处开始，将后面的元素，插入之前的有序列表中使之仍保持有序
 */
public class ArrayDemo05 {
    public static void main(String[] args) {
        int[] array={12,20,42,80,10,30,11,12};
        //定义一个外层循环
        //我们从1索引开始插入所以要把i初值设置为1
        for (int i = 1; i < array.length; i++) {
            //为什么要设置j=i呢？
            //为什么j--呢？
            //为什么j>0呢？
            /*
            思路：
            首先对array[i]和array[i-1]相比，
            然后若array[i]<array[i-1],让二者值进行互换。
            比如，array[i]=1,array[i-1]=3,array[i-2]=0的，互换后发现，array[i-1]=1,array[i]=3;
            这时候再进行while循环发现，不对呀，这不继续循环了呀。
            array[i]<array[i-1]为false就跳出循环了。
            所以要进行让i--，让i-1与i-2进行比较就可以继续进行循环了。
            循环是可以了，但是i--不能小于0呀，所以在循环中要让i>0.
            但是i--与上面的for循环i++有冲突了呀。所以要拿个变量进行赋值i。所以定义一个j=i;并且循环条件改成j>0.
            这样即可实现了插入排序
            */
            int j=i;
            while(j>0&&array[j]<array[j-1]){
                int t=array[j];
                array[j]=array[j-1];
                array[j-1]=t;
                j--;
            }
        }
        System.out.println(Arrays.toString(array));
    }
}