开篇

聊完选择排序，这篇我们来聊聊插入排序。

设想下你现在要安排一队人按照身高从低到高排序站立，你的排序方法很可能是一个人一个人来，将每一个人插入到当前已经有序的队列中去，为了给要插入的人（元素）腾出空间，我们需要将当前队列中所有比待插入人长得高的人向右移动一个人的位置，以给待插入的人腾出空间。

这就叫插入排序。

正文

这次我们直接上图来具象化展示插入排序的过程：

插入排序过程，图源维基百科

下面我们直接上嵌套循环版本的代码，递归版本的代码且略过不写，还是以 Java 为例：

/**
     * @see: 插入排序的 Java 实现，使用快慢指针思路
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortInsert(int[] array){
        //外层我们先假定数组第一个元素已部分有序，
        //即第一个元素已在它该在的位置，
        //从数组第二个元素开始遍历，当然数组长度可能小于2
        for (int slow = 1; slow < array.length; slow ++){
            //待插入元素 array[slow]
            int insertion = array[slow];
            //内循环遍历，主要为确定待插入元素array[slow]的待插入位置
            int fast = slow - 1;//内循环快指针
            for (; fast >= 0; fast --){
                if (array[fast] > insertion){
                    array[fast + 1] = array[fast];
                }else {
                    //待插入元素的待插入位置，总是从后往前看，最后一个值比它大的那个位置，
                    //值比它大的那些值整体往后移动一个位置
                    break;
                }
            }
            //插入待插入元素，即最后一个值比它大的那个位置
            array[fast + 1] = insertion;
        }
    }

上篇聊选择排序我们说到其是一种运行时间和输入无关的算法，而插入排序是典型的运行时间严重依赖输入的算法，插入排序运行的平均和最坏时间复杂度都是平方级别的 О(n²)，但如果待排序数组是一个已经整体有序的数组，则只需要线性级别的时间复杂度 О(n) 即可运行完算法。

尾巴

下篇，我们聊希尔排序。