1.插入排序概述

插入排序的基本方法是：每次将一个待排序的数据元素，按其key的大小，插入到已经排序好的一组数据元素中，直到所有数据元素全部插入为止。

根据已经排好序的数据元素序列中寻找插入位置的不同方法，可以将插入排序分为：直接插入排序、二分插入排序、希尔排序。

2.直接插入排序

直接插入排序采用最直接的方法将元素插入到已经排好序的序列中。

2.1.直接插入排序过程

直接插入分为三步：

第一步，找到插入的位置；

第二步，将插入位置起的元素往后移动一个位置；

第三步，将数据写入需插入的位置。

2.2.实现代码

直接插入排序实现代码如下所示

    void simpleInsertSort(T[] a, int size) {
        int k;
        T tmp;
        for (int j = 1; j < size; j++) {
            tmp = a[j];
            for (k = j - 1; k >= 0; k--) {
                if (tmp < a[k]) {
                    a[k + 1] = a[k];
                } else {
                    break;
                }
            }
            a[k + 1] = tmp;
        }
    }

对数组T[] a进行插入排序。空间复杂度为O(1)。

2.3.时间复杂度

最好的情况下，待排序的数组是有顺序的，则在排序过程中，不会涉及到第二步的操作，即不需要移动已有元素，时间复杂度为O(N)。

最坏的情况下，待排序数组是逆序的，在排序过程中，需要完整地执行以上三步，时间复杂度为O(N^2)。

3.直接插入排序适用场景

直接插入排序适合少量元素的简单排序算法。