1、基本思想
把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只有一个元素（第一个），无序表中包含 n - 1 个元素（1,2,…,n-1），排序过程每次从无序表取出第一个元素，把它的值依次和有序表的元素进行比较，将它插入到有序表合适的位置，使之成为新的有序表。
2、图解
3、代码实现
package cn.klb.datastructures.sort;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 实现数组的插入排序
* @Date: Create in 2023/4/3 23:33
* @Modified By:
*/
public class Insert {
/**
* 插入排序
*
* @param arr
*/
public static void sort(int[] arr) {
int insertVal = 0; // 保存待插入元素的值
int insertIndex = 0; // 保存待插入元素的索引
for (int i = 1; i < arr.length; i++) {
insertVal = arr[i]; // 先把待插入的值保存起来
insertIndex = i - 1; // 先假设要插在有序表最后一个位置
// 判断：
// 1.待插入的值比待插入位置的值小，则继续往前看有没有更小，直到找不到更小的，就确定了待插入位置
// 2.当 insertIndex 为0，表示找到尽头了，有序表所有值都比待插入值大，直接插入到最前面
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
// 待插入位置的值往后走，腾出位置
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
// 如果待插入位置和预设的一样，就省的换位置了
if (insertIndex != i - 1) {
arr[insertIndex + 1] = insertVal;
}
}
}
}
4、时间复杂度
通过代码可以看出，总共一个for循环，里面嵌套一个while循环。
假设比较次数为C，交换次数为S。
一般情况下，对于内循环while中元素的比较次数C对于 insertIndex 的每个值最多是 insertIndex+1 次，因此对所有的 insertIndex 求和得到总数为 2+3+…+n=O(n²)。
最好的情况下，序列已经是从小到大有序。这时，内循环每次比较都不满足条件，不会进行交换，于是运行次数为 1+1+,…,+n = O(n)。
最坏的情况下，序列从大到小排列。这时，运行次数就直接满足一般情况下的“最多”，为O(n²)。
时间复杂度都是看最复杂的，因此，选择排序的时间复杂度为O(n²)。
可以看出，如果待排序序列几乎被排序，那么插入排序的效率会很好。反之，会很低效。由于这种变化差别很大，因此值得去分析该算法的平均情形的行为，但实际上，插入排序的平均情形时间复杂度也是O(n²)。
首先要明白一点，平均时间复杂度不是最好情况和最坏情况加起来除以二。
以一个数字序列为例，首先要明白一个概念“逆序”，所谓逆序指的是具有性质 i<j 但a[i]>a[j] 的序偶（a[i],a[j]）。比如一个序列是{34，8，64，51，32，21}，对每一个元素找出序偶，分别是：（34，8）、（34，31）、（34，21）、（64，51）、（64，32）、（64，21）、（51，31）、（51，21）以及（32，21）总共9个逆序。这正式需要由插入排序隐含的执行的交换次数，交换一次两个不按顺序排列的相邻元素恰好消除一个逆序，然后一个排过序的数组没有逆序。
由于算法有除了交换以外的O(N)其他操作（包括比较）。因此插入排序的运行时间是O(I+N)，其中I为逆序数。于是，若逆序数为O(N)，则插入排序以线性时间运行。
假设有一个包含n个整数的数组，这个数组不存在重复元素，数组的数据是前n个整数的某个排列。那么这个数组的平均逆序数为 n(n-1)/4 。（证明过程可百度查询）
通过交换相邻元素进行排序的任何算法的平均时间复杂度都为O(n²)。（证明过程可百度查询）
5、稳定性
通过代码分析可知，无序列表是从后向前跟有序列表一一对比找出可插入位置，所以当存在两个相同数字，根据本例的代码，其前后相对位置是不会改变的，因此是稳定的。
但是， 当找出可插入位置是逻辑是对有序列表从前向后扫描，那就会破坏两个相同数字的前后关系，导致不稳定。
需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
总结：插入排序是稳定的。
6、测试
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.sort.*;
import org.junit.Test;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 排序测试
* @Date: Create in 2023/4/3 21:32
* @Modified By:
*/
public class SotrTest {
@Test
public void testInsert() {
int[] arr = new int[800000];
for (int i = 0; i < 800000; i++) {
arr[i] = (int) (Math.random() * 800000);
}
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date date1 = new Date();
System.out.println("-----" + sdf.format(date1) + "-----");
Insert.sort(arr);
Date date2 = new Date();
System.out.println("-----" + sdf.format(date2) + "-----");
// 80万的随机数据进行插入排序，我的电脑花了大约54秒（比选择排序更快）
}
}