1）将数组看成无序和有序两段，默认第一个元素在有序段，后面n-1个元素在无序段
2）每次取出无序段的第一个元素，在有序段找到合适的位置插入
3）如何找到合适的插入位置?
4）从有序段的最后一个元素向前遍历，假如每次遍历的元素所在索引就是插入位 insertIndex
5）如果是升序，insertVal < arr[insertIndex] 就表示还没有找到插入位，insertVal 最终的插入位肯定是在insertIndex前的
6）就将 arr[insertIndex] 的值向后存储一位，给待插入的元素留空间, insertIndex--, 向前继续查找插入位
7）如果一开始 insertVal > arr[insertIndex]，那么就不需要遍历，直接插入到 insertIndex + 1的位置
代码实现：
public static void insertSort(int[] arr){ //定义待插入的数 int insertVal; int insertIndex; for (int i = 1; i < arr.length; i++) { insertVal = arr[i]; insertIndex = i - 1; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //假如待插入值是12，理应插入位应在4的后面，循环会在4的索引停住，则需要插入到insertIndex+1 if(insertIndex!= (i-1)){ arr[insertIndex + 1] = insertVal; } } }