插入排序的思想

插入排序算法是一个比较简单好理解的算法。直接的例子就是玩扑克的时候，想象一下，分牌的时候，大家轮流的从一组牌中抽取最上面的一张，然后将它以某种顺序插入到我们的左手中。比如，我们想要从小到大排列我们的扑克牌。

那么第一次，抽到了2，我们的左手还没有任何牌，直接放到左手上。

左手：[2]

第二次，我们抽到了9，由于已经存在2了，因此，我们将9放在2的右边。

左手：[2, 9]

第三次，我们抽到了1（A），我们会很自然的将它塞进2的左边。

左手：[1, 2, 9]

以上这个过程如此循环。在这个过程中，不得不佩服人的大脑可以瞬间知道该塞在哪里。眼睛一瞟，就能快速的知道应该放到哪个位置附近，然后再仔细的查看，稍加比较，就可以得出结果。
但是计算机就不行了，它无法像人眼那样一下子获取到全局的信息，它只能一个一个的比较。另一方面，它在插入的时候，操作数据是时候，也不像人类操作扑克那样的方便。

插入排序的总体思想，我们已经知道了，接下来就是如何实现了。

思路

我们拿到的是一个数组。arr，我们可以假设，第一个数据是排好的，以它作为基准，从第二个数据开始进行处理。

我们拿第二个数据arr[1]和第一个数据arr[0]进行比较，如果arr[1] >= arr[0]，那就没有什么需要操作的，它们两个也是排好的，如果arr[1] < arr[0]，那么，我们就需要将它们交换位置。

考虑一个更通用的情况，比如：

1, 3, 4, 5, 2, 7 // 初始化的情况
0, 1, 2, 3, 4, 5 // 这是index

index=1开始，3大于1，那么index++
index=2，4大于3，那么index++
index=3，5大于4，那么index++
index=4，2小于5，那么交换5和2的位置，并index--

1, 3, 4, 2, 5, 7 // 交换后
0, 1, 2, 3, 4, 5 // 这是index

index=3，2小于4，继续交换，index--

1, 3, 2, 4, 5, 7 // 交换后
0, 1, 2, 3, 4, 5 // 这是index

index=2，2小于3，继续交换，index--

1, 2, 3, 4, 5, 7 // 交换后
0, 1, 2, 3, 4, 5 // 这是index

index=1，2大于1，完事了

???刚刚我处理到哪里了???

由于没有保存开始处理的index，导致不知道从哪里继续开始。
所以，不断交换的index和开始处理的index要独立保存即可

实现

public class InsertSort implements ISort {

    @Override
    public int[] sort(int[] data) {

        if (data == null) {
            return null;
        }

        if (data.length == 1) {
            return data;
        }

        for (int i = 1; i < data.length; i++) {
            int finder = i; // 将当前要处理的index保存住
            int val = data[i];
            while (finder >= 0 && val < data[finder - 1]) {
                data[finder] = data[finder - 1]; // 交换数据
                data[finder - 1] = val;
                finder--; // 继续和之前的比较
            }
        }

        return data;
    }
}

wiki上标准的写法

public void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

总得来说，插入排序是思路和实现都比较简答的排序方法。
最好情况时间复杂度为：
最坏和平均情况时间复杂度都是：