白话排序算法--插入排序

浏览数：17 / 时间：2015年06月08日

前言:

　　昨天下午写好了冒泡排序后，紧跟其后，今天跟新上插入排序算法。

插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

情景描述：

　　紧接冒泡排序，每次同学们都屡试不爽，但是学生越来越多了，老师发现每次排完队，就耽搁了大半节课时了，说道：“咱不用冒泡了，有点OUT了，今天来插入排序”。这时体育老师担任起了数学老师的职责，又给同学们讲了种排队方式--插入排序。

开始以第一位同学为基准，由第二个同学开始向前和第一位同学比较，个头高了不动，低了换位
第三个同学要先和自己前面的第二位同学比较，如果低了，和第二换位，然后再向前和第一比较，低了再换，否则阻断，不再比较
从前往后依次执行步骤2，依次出来一位同学，每次和自己前面的同学进行比较，找到一个合适位置插入，其余学生后移

合适位置：前一位同学等于或低于自己身高，并且后一位同学高于自己身高

　　按照这个方式，同学们一个个依次找准位置，再也不用每次相邻的都比较，而且找到位置后就不必再往前面比较了......

　　上图中，深色部分为每次已排完序的列表，红色指引末端为要插入元素，其余枝节为即将与之一一比较的元素。

代码片段：

/**
     * 插入排序，默认第一位已经排好序，从第二位开始依次向前比较,确定自己的位置后插入，即前一位小余或等于当前，且后一位大于当前。
     * 插入后，自己新位置后面的元素依次向后移位， 完成一轮插入排序
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            if (arr[i - 1] > arr[i]) {
                int k = arr[i];
                int j = i;
                while (j > 0 && arr[j - 1] > k) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = k;
            }
        }
        return arr;
    }