插入排序算法思路

从小到大排序时

插入排序算法原理：
将数组中的数据分为2个区域：已排序区间和未排序区间。
初始时已排序区间只有一个元素，就是数组中的第一个元数
核心思想就是取未排序区间中的元素，在已排序区间中找合适插入位置将其插入，保证已排序区间数据一直有序
重复这个过程直到未排序区间中元素为空，算法结束。

时间复杂度：O(n)~O(n^2)之间。

最坏情况下（即从大到小排列） O(n^2) 逆序情况下代码执行最多次的是 value < arr[j],第一趟执行 1次，第二趟执行 2次… n-1次，就是一个等差数列求和近似= n*(n-1)/2。

最好情况下O(n);当已经从小到大排好序后，每一趟下来都会进入else{break}。

空间复杂度：O(1)，插入排序是原地交换的排序算法，没有申请额外空间。
插入排序是稳定的排序算法。例如 {1,2,2,0},由于移动条件是 if(value < a[j]),当下标i=2时value=arr[i],j=1，第一个2不会与第二个2交换位置。

一、核心代码

    /**
     * 插入排序算法原理：
     * 将数组中的数据分为2个区域：已排序区间和未排序区间。
     * 初始时已排序区间只有一个元素，就是数组中的第一个元数
     * 核心思想就是取未排序区间中的元素，在已排序区间中找合适插入位置将其插入，保证已排序区间数据一直有序
     * 重复这个过程直到未排序区间中元素为空，算法结束。
     *
     * @param arr 原数组
     * @return 排序后的数组
     */
    private static int[] insertionSort(int[] arr) {
        if (null != arr && arr.length > 0) {
            // 第一层是未排序区间每取一个到已排序区间找合适的位置插入
            for (int i = 1; i < arr.length; ++i) {
                // i的位置会被覆盖，需要拿出来
                int value = arr[i];
                // 已排序区域的末尾一定是未排序区域的前一个位置
                int j = i - 1;
                for (; j >= 0; --j) {
                    if (value < arr[j]) {
                        // 移动数据空出位置来
                        arr[j + 1] = arr[j];
                    } else {
                        break;
                    }
                }
                // 插入数据,挪完之后j--了,所以这里是j+1加回一个
                arr[j + 1] = value;
            }
        }
        return arr;
    }

二、测试用例

package arithmetic.ecut.com.排序.a_插入排序;

/**
 * 插入排序算法
 *
 * @author 起凤
 * @description: TODO
 * @date 2022/4/5
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 4, -1, 8, -1};
        int[] sort = insertionSort(arr);
        print(sort);

        int[] arr1 = {-1, 7, 1, 4, 5, 8, 7};
        int[] sort1 = insertionSort(arr1);
        print(sort1);
    }
    
    private static int[] insertionSort(int[] arr) {
        if (null != arr && arr.length > 0) {
            // 第一层是未排序区间每取一个到已排序区间找合适的位置插入
            for (int i = 1; i < arr.length; ++i) {
                // i的位置会被覆盖，需要拿出来
                int value = arr[i];
                // 已排序区域的末尾一定是未排序区域的前一个位置
                int j = i - 1;
                for (; j >= 0; --j) {
                    if (value < arr[j]) {
                        // 移动数据空出位置来
                        arr[j + 1] = arr[j];
                    } else {
                        break;
                    }
                }
                // 插入数据,挪完之后j--了,所以这里是j+1加回一个
                arr[j + 1] = value;
            }
        }
        return arr;
    }

    private static void print(int[] sort) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < sort.length; i++) {
            builder.append(sort[i]).append(",");
        }
        System.out.println(builder);
    }
}