18.直接插入排序

1.思路分析

将一组数据分为两组，一组为排好序的，一组为未排序的，每次从未排序的数组中选一个元素插入到已排序的数组合适的位置，需要进行数组长度-1次
具体实现：

• 第一轮将第二个元素与第一个元素比较，插入到合适的位置
• 第二轮将第三个元素与前两个元素比较，插入到合适的位置
• 第n-1轮将第n个元素与前面n-1个元素比较 ，插入到合适的位置

2.代码实现

package com.yc.day04;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {20,13,90,3,412,34,32,324};
        insertSort(arr);
    }
    public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++) {

            //要插入的值
            int insertVal = arr[i];
            int insertIndex = i - 1;

            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //退出循环表明找到了要插入的位置
            arr[insertIndex + 1] = insertVal;
            System.out.println("第"+i+"轮排序完：");
            System.out.println(Arrays.toString(arr));
        }
    }
}