排序算法：插入排序

插入排序的原理和玩扑克牌很像，假设你拿到了一堆牌，如果里面基本有序，那你需要进行的操作就少，如果很多无序你就需要处理得多。插入排序相当于你一副牌从最左边开始整理牌的顺序，第一张肯定是有序的，开始看第二张牌，第二张牌小于第一张的话就放第一张左边，不然的话就结束第二张牌的插入处理，开始处理第三张牌，然后判断第三张牌是放原位置呢还是插入到哪个位置。

实现思想，n个元素的数组里，元素下标为0到n-1，arr[0]有序，那么从位置1开始往后进行比较插入，arr[1]大于arr[0]就直接结束循环，不然就插入到arr[0]的左边。然后开始查找arr[2]的正确位置，查找arr[2]的时候它左边的元素已经有序了。假设比较到了arr[k]，arr[k]的正确位置有三种情况，第一种就是它恰好大于左边所有元素，所以不用动，直接结束查找位置的逻辑，不用管arr[k]了，开始查找arr[k+1]的正确位置。第二种情况就是arr[k]小于左边的左右元素，所以最后就是需要arr[0]~arr[k-1]整体右移1位，把arr[0]腾出来给arr[k]，但是右移之前需要一个临时变量先保存arr[k]的值，不然它就丢了。第三种情况就是arr[k]恰好插入左边排好序的中间某个位置，就是如同arr[z] <= arr[k] < arr[z+1]的情况，这时候需要插入arr[z]和arr[z+1]之间（看起来是这样，但是实现的话是需要把arr[z+1]~arr[k-1]的元素整体右移一位，同时需要临时变量保存arr[k]的值，最终把arr[k]的临时变量值放到位置z+1处）。

所以实现起来就很简单了，第一种情况直接结束某个元素的位置比较的循环了，第二种和第三种情况是有共同点的，1是都需要临时变量temp，2是都需要右移元素，所以可以先用temp把arr[k]临时保存一下，只要不是第一种情况，就可以一边获取正确位置一边右移元素，直到找到某个适合插入的位置（元素中间，或者所有元素左边）。

实现

Java实现

public static void insertSort(int [] arr){
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > temp){
            // 元素右移
            arr[j + 1] = arr[j];
            j--;
        }
        // 要么没进循环，要么就是在中间某个位置，要么就是所有元素比完了发现小于所有元素
        // 没进循环，j + 1就是i，所以赋值两端原本就相等，不影响后续处理
        // 如果在中间某个位置，while、内部已经移动过元素，所以temp直接放j+1
        // 如果小于左边所有元素，此时j已经递减为了-1，此时把arr[j+1]也就是arr[0]的值更换为temp
        arr[j + 1] = temp;
    }
}

时间复杂度的话是分情况的，最好情况就是原本都有序，所以只需要遍历n个元素，时间复杂度为O(n)。最坏情况就是每次都需要比较而且都需要插入到最左边，内层循环的次数分别是1, 2, 3 ……n-1,，所以时间复杂度为1+2+3+……(n-1)=(n-1)×n/2，因此时间复杂度为O(n²)，平均复杂度也为O(n²)。这也是原地排序，所以空间复杂度为O(1)。稳定性的话，由于比较到相等的元素时，右边的元素还是会优先放右边，所以插入排序是稳定的，但是实现的细节需要注意，如果比较条件不对的话可能结果正确，但算法不稳定，arr[j] > temp这里不能写成arr[j] >= temp。

总结

时间复杂度（最好）：O(n)

时间复杂度（最差）：O(n²)

时间复杂度（平均）：O(n²)

空间复杂度：O(1)

稳定性：稳定