插入排序

1.插入排序概念

将数组分为两个区域，排序区域和未排序区域，每一轮从未排序的区域中选取第一个元素，插入到排序区域。（需保证顺序）；
重复以上步骤，直至数组有序。
举个例子：

int[] a = {9, 3, 7, 2, 5, 8, 1, 4};

刚开始选取第一个元素即9为排序区，
第一轮选取到3，因为3<9，故3插入到9前面，此时排序区为{3,9}；
第二轮选取到7，因为3<7<9，故插入至它们中间，此时排序区为{3,7,9}；
......
以此类推

2.编程思路

1. 定义 i 表示待插入元素的索引，从1开始
2. 定义 t 表示待插入的元素值
3. 定义 j 表示已排序区域的最后一个元素索引
4. 如果待插入元素小于排序区域中的最后一个，将原最后一个往后移一位

3.代码实现

package array;

import java.util.Arrays;

/**
 * @author: 邹祥发
 * @date: 2021/10/15 13:21
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
        insert(a);
    }

    private static void insert(int[] a) {
        // i 表示待插入元素的索引，从1开始
        for (int i = 1; i < a.length; i++) {
            // t 表示待插入的元素值
            int t = a[i];
            // j 表示已排序区域的最后一个元素索引
            int j = i - 1;
            while (j >= 0) {
                if (t < a[j]) {
                    // 待插入元素小于排序区域中的最后一个，将原最后一个往后移一位
                    a[j + 1] = a[j];
                } else {
                    // 退出循环，减少比较次数
                    break;
                }
                j--;
            }
            a[j + 1] = t;
            System.out.println(Arrays.toString(a));
        }
    }
}

输出结果：
[3, 9, 7, 2, 5, 8, 1, 4]
[3, 7, 9, 2, 5, 8, 1, 4]
[2, 3, 7, 9, 5, 8, 1, 4]
[2, 3, 5, 7, 9, 8, 1, 4]
[2, 3, 5, 7, 8, 9, 1, 4]
[1, 2, 3, 5, 7, 8, 9, 4]
[1, 2, 3, 4, 5, 7, 8, 9]