2018-07-27 插入排序

插入排序的思想是数组中每一个元素都跟它前边的每个元素比较，并插入到合适位置。
若前面的一个数字比它大，则交换它们两个的位置，然后再次比较该位置前一位数是否仍然比其大，若成立，则继续交换，否则轮到下一个检测位重复上面的操作，这样，所有位上面的数字都能够与其前面的数字进行比较并占到符合自己的位置，相比于选择排序，插入排序的一个优点是提前终止，不用遍历整个数组，因此，插入排序应该要比选择排序的效率更加的高效。

画图分析整个过程：

2018-07-27 插入排序

实现代码很简单。

    public static void main(String[] args) {
        int aa[] = {8, 6, 2, 3, 1, 5, 7, 4};
        System.out.println("aa[] =" + Arrays.toString(aa));
        insertSort(aa, 0, 8);
        System.out.println("aa[] =" + Arrays.toString(aa));
    }
    private static void insertSort(int a[], int off, int len) {
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0 && a[j-1] > a[j]; j--) {
                // 交换值，这里比较耗时。（耗时）
                int t = a[j];
                a[j] = a[j-1];
                a[j-1] = t;
            }
        }
        return;
    }

运行结果:

排序 前：[8, 6, 2, 3, 1, 5, 7, 4]
排序 后：[1, 2, 3, 4, 5, 6, 7, 8]

以上插入算法还可以再进行优化。经过分析 发现程序大部分时间都花费在了 值得交换。所以可以针对这里再进行优化一下
可以这样修改原来的插入排序算法，首先复制一份待插入的值（我们暂且标记为插入位，后文都为了方便都记做插入位），然后把该值一直与插入位前面的数字比较（该步骤与原来的插入排序算法一样），但是，我们每次比较，如果前面的数字比插入位大，我们不进行交换，而是让插入位被赋值为前面的大数，以此类推，若前面一直有数字比插入位大，则都让这些数字“往后挪一位”，直到发现没有比自己更高的数字了，就把插入位的数值直接赋值给现在这个位置
实现代码如下：

    private static void insertSort2(int a[], int off, int len) {
        for (int i = 1; i < len; i++) {
            int temp = a[i];
            int j;
            for (j = i; j > 0 && a[j-1] > temp; j--) {
                a[j] = a[j-1];
            }
            a[j] = temp;
        }
        return;
    }

经过改进之后的插入排序，效率更高。