原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
要点：设立哨兵，作为临时存储和判断数组边界之用。
private static void sortInsert(int[] array) {
//逐步扩大有序区
for (int i = 1; i < array.length; i++) {
int key = array[i];
//分别为无序区i和有序区j指针
int j = i - 1;
//寻找插入位置
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
//插入元素
array[j + 1] = key;
printArray(String.format(Locale.getDefault(), "key = %2d , j = %2d : ", key, j + 1), array);
}
}
运行结果：
数组： 55 22 66 33 11 99 77 44 88
插入排序：
key = 22 , j = 0 : 22 55 66 33 11 99 77 44 88
key = 66 , j = 2 : 22 55 66 33 11 99 77 44 88
key = 33 , j = 1 : 22 33 55 66 11 99 77 44 88
key = 11 , j = 0 : 11 22 33 55 66 99 77 44 88
key = 99 , j = 5 : 11 22 33 55 66 99 77 44 88
key = 77 , j = 5 : 11 22 33 55 66 77 99 44 88
key = 44 , j = 3 : 11 22 33 44 55 66 77 99 88
key = 88 , j = 7 : 11 22 33 44 55 66 77 88 99
