算法概述

简单地说，插入排序就是将待排序列中未排序的元素插入到前面已经排序好的子序列当中的过程，直到最后一个元素。
举个例子，对数组{9,3,7,2,66,22}进行插入排序的过程可以分为以下几步：
1，我们将当前的有序子序列称为A，初始时A只有一个元素 9
2，从A后面开始，将元素插入到A中合适的位置，使A仍然有序，同时A的大小加1
3，重复步骤2，直到最后一个元素

步骤2插入的过程：
因为A已经有序，所以将某个元素e插入A，只要从A的末尾开始扫描，假设当前扫描到的元素为f，如果e比f小，就将f后移一位（相当于将e的位置腾出来了），如果e不比f小，则此次扫描完成，最后将e放在最后扫描终止的位置上。

下面的图片较为形象地表达了插入排序的过程：

实现代码 (Java)

public void insertSort(int[] input) {
        int i, j, tmp;
        for (i = 1; i < input.length; i++) {
            tmp = input[i];
            for (j = i; j > 0 && tmp < input[j - 1]; j--) {
                input[j] = input[j - 1];
            }
            input[j] = tmp;
         }
}

复杂度

插入排序存在最好情况和最坏情况。最好情况就是，序列已经有序了，在这种情况下，需要进行的比较操作为 (n-1)次，最坏的情况是序列是反序的，此时需要进行的比较操作为n*(n-1)/2次，插入排序的平均时间复杂度为O(n²)。由于不需要额外的空间，插入排序的空间复杂度为O(1)。

适用场景

插入排序不适合数据量比较大的排序应用。但是，如果需要排序的数据量很小，或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。