内存排序(三)——插入排序

核心过程

将原数组里的数，按有序和无序分为两部分，将无序部分的数逐个插入有序部分中。
重点：插入过程中，保持新数组是有序的。
所以核心过程是：将一个数插入一个有序数组，并保持数组有序。

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：直接插入还有二分优化和希尔排序两种优化方式。待续。