1.插入排序简介

2.插入排序图解

3.代码

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        InsertSort.insertSort(arr);
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        //{101,34,119,1}
        //int i = 1：第1个数为有序表
        for (int i = 1;i<arr.length;i++) {
            //待插入的数
            int insertVal = arr[i];//insertVal在第一轮排序时是34
            //insertVal：待插入的位置
            int insertIndex = i-1;
            //insertVal<arr[insertIndex]:表示insertVal没有找到位置
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]后移，给insertVal让出一个位置
                //待插入位置前移
                insertIndex--;
            }
            //找到位置时退出循环
            //insertIndex+1:while中insertIndex--后再判断，所以加一
            arr[insertIndex+1]=insertVal;
            System.out.println("第"+i+"趟排序："+Arrays.toString(arr));

        }
    }
}