插入排序【算法导论】

注：学习算法导论，按照标准伪代码理解翻译为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;
    }
}