核心过程
将原数组里的数，按有序和无序分为两部分，将无序部分的数逐个插入有序部分中。
重点：插入过程中，保持新数组是有序的。
所以核心过程是：将一个数插入一个有序数组，并保持数组有序。
public static void insertionSortCore(int[] list, int begin, int end, int value){
int index = end;
for (; index >= begin && list[index] > value; index--) {
list[index + 1] = list[index];
}
list[index + 1] = value;
}
迭代过程
public static void insertionSortIteration(int[] list){
for (int i = 1; i < list.length; i++){
insertionSortCore(list, 0, i - 1, list[i]);
}
}
合并两过程的写法
public static void insertionSort(int[] list){
int rightBegin, rightEnd;
for (rightBegin = 1; rightBegin < list.length; rightBegin++){
int value = list[rightBegin];
for (rightEnd = rightBegin - 1; rightEnd >= 0 && list[rightEnd] > value; rightEnd--) {
list[rightEnd + 1] = list[rightEnd];
}
list[rightEnd + 1] = value;
}
}
PS：直接插入还有二分优化和希尔排序两种优化方式。待续。
