特点

效率低，但是稳定，不受数据分布影响。

原理

1. 简单理解，就是假设有长度为n的数列
2. 假设前i个数为有序（i可为1）
3. 从i个数后选择一个数，按照大小顺序插入i列数中，保持i数列的有序
4. 不断选择直至n数列都插入到i数列中，且i数列保持有序

code

public static void insertSort(int[] arr) {
	int temp = 0;
	for (int i = 1; i < arr.length; i++) {
		int j = i - 1;
		//使用中间值存储，否则下面循环会改变a[i]的值
		temp = arr[i];
		//从i前一位开始，当值大于i时，向后位移一位，也就是将大于a[i]的值整体后移一位
		for (; j >= 0 && arr[j] > temp; j--) {
			arr[j + 1] = arr[j];
		}
		//当遍历到不大于第i位时，将第i位插入到对应位置
		arr[j + 1] = temp;//将a[i]插入到a[j]后面
	}
}