插入排序的思想

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

那么第一次，抽到了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 // 这是indexindex=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 // 这是indexindex=3，2小于4，继续交换，index--1, 3, 2, 4, 5, 7 // 交换后0, 1, 2, 3, 4, 5 // 这是indexindex=2，2小于3，继续交换，index--1, 2, 3, 4, 5, 7 // 交换后0, 1, 2, 3, 4, 5 // 这是indexindex=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;    }}

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