1、算法核心

对数组中的元素进行遍历，从第二个元素开始，遇到的数值小的，把这个数值前面的数字向后面移动一个单位，占掉小数字的位置，出现了一个空的位置，最终这个空的位置，继续移动到达合适的位置，这个位置就是给前面的小数值留下的；

2、实现代码

package com.luobin.DataStructure.排序;

/**
 * @author LuoBin
 * @version 1.0
 * @date 2021/8/8 8:45 下午
 */
public class Insert {
    public static void main(String[] args) {

        int[] testInsert = new int[]{0, 1, 2,9,3,2,1};
        insertionSort(testInsert);

    }

    public static int[] insertionSort(int[] array) {
        int len;
        // 基本情况下的数组可以直接返回
        if(array == null || (len = array.length) == 0 || len == 1) {
            return array;
        }
        int current;
			// 	对于循环的次数，第一个不用排，需要 len - 1 次循环
        for (int i = 0; i < len - 1; i++) {

            // 第一个数默认已排序，从第二个数开始
            current = array[i + 1];

            // 前一个数的下标
            int preIdx = i;

            // 拿当前的数与之前已排序序列逐一往前比较，
            // 需要进行比较的当前的数据比前一个数据小，把前面大的数据往后面放一放，小的数据往前面放
            while (preIdx >= 0 && current < array[preIdx]) {

                // 把前面比较大的数字往后面放一放
                array[preIdx + 1] = array[preIdx];
                preIdx--;
            }

            // while循环跳出说明找到了位置
            array[preIdx + 1] = current;
        }

        for (int i = 0;i < array.length;i++) {
            System.out.println("进行排序之后的算法是：" + i);
        }
        return array;
    }
}