注：学习算法导论，按照标准伪代码理解翻译为java实现，如有兴趣理解整个过程的细节，建议阅读《算法导论》第二章：2.1插入排序。
- 标准实现：从左往右排序
void insertionSort(int[] arr) {
int i;
for (int j = 1; j < arr.length; j++) {
i = j - 1;
int key = arr[j];
// 当i大于当前key元素时一直向前继续比较
while (i >= 0 && arr[i] > key) {
// 满足while条件，说明 i 对应的元素一定大于 i + 1 对应的元素和key
// 所以 i 对应的元素向后移动一位
arr[i + 1] = arr[i];
// i 再向前移动
i = i - 1;
}
// 循环结束后，i + 1 指向的位置肯定为空缺的
// 此时key 满足 key > A[i] and key <= A[i + 2]
// 所以将key置于 i+1 的位置
arr[i + 1] = key;
// 每次循环结束都能保证key左侧的元素有序
// System.out.println(Arrays.toString(arr));
}
}
- 本章练习：从右往左，降序倒排
/**
* 从后往前排
* @param arr
*/
void insertionSortDownTo(int[] arr) {
int i;
for (int j = arr.length - 2; j >= 0; j--) {
int key = arr[j];
i = j + 1;
while (i < arr.length && arr[i] < key) {
arr[i - 1] = arr[i];
i++;
}
arr[i - 1] = key;
}
}
