import java.util.Arrays;
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {5,4,3,2,1,-1,-5,-3};
        System.out.println("未排序数组："+ Arrays.toString(arr));
        insertSort(arr);
        System.out.println("未排序数组："+ Arrays.toString(arr));
    }
    public static void insertSort(int[] arr){
        for (int i=1;i<arr.length;i++){//插入排序从第二个元素开始进行，// 所以这里i（作为索引）设为1，循环次数为arr.length-1;
            int insertIndex = i;//待插入元素的索引位置，循环中进行位置的移动
            int insertValue = arr[i];//待插入元素的值，循环中值不会变
            while (insertIndex - 1 >= 0 && insertValue < arr[insertIndex-1]){//当要排序的元素比前一个元素大时，并且待插入的元素的索引位置大于0（不在第一位）时，进入循环
                arr[insertIndex] = arr[insertIndex-1];//每次arr[i]<arr[i-1],就把arr[i-1]的值往后移，直到arr[i]>arr[i-1]
                insertIndex--;
            }
            arr[insertIndex] = insertValue;
            //insertValue 在比较过程中一直没变，最后一步将insertValue的值赋给insertIndex所指的元素
        }
    }
}