从大的排序类上来说，直接插入排序和希尔排序都属于插入类排序。这类排序和生活中玩的扑克牌很像，一边摸牌，一边理牌。摸到一张新牌时，我们都要把这张牌和手中的牌对比一下，然后考虑这张牌该插入到哪个位置；基于这种想法，所以有了插入排序类。

直接插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录数增 1 的有序表。实现起来也比较简单：

void insertSort(int arr[], int len) {
    int i, j, sentry;
    for (i = 1; i < len; i++) { // 默认第一个元素是有序的，直接从第二个元素开始
        if (arr[i] < arr[i-1]) {
            sentry = arr[i]; // 哨兵记录待插入的元素
            for (j = i - 1; (arr[j] > sentry) && (j >= 0); j--) {
                arr[j + 1] = arr[j];
            }
            arr[j+1] = sentry;
        }
    }
}

算法从第二个元素开始即可，那么我们考虑的就是，第二个元素插入到已有的有序序列哪个位置，通过逐一比较来找到合适的位置，如此反复循环，直到整体序列有序。算法的代码实现也比较简单，如上。

最好情况下，直接插入排序的时间复杂度为 O(n)，最坏情况下时间复杂度为 O($n^2$)，如果排序记录是随机的，根据概率相同的原则，我们得出直接插入排序的时间复杂度为 O($n^2$)。空间复杂度上，只需要一个记录的辅助空间，可以忽略。

希尔排序

希尔排序是 D.L.Shell 在 1959 年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是 O($n^2$)，希尔排序算是突破了这一复杂度的第一批算法。

void shellSort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
}

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个 “增量” 的记录组成的一个子序列，实现跳跃式的移动，来提高排序的效率。

维基百科对希尔排序的描述很好理解：

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了；点击前往维基百科。

所以希尔排序的增量的选择就非常关键了，到目前增量具体选择多少还没有确定的数字。大部分我们写的代码中都是从 $n/2$ 开始的，需要注意的是增量序列的最后一个增量值必须等于 1 才行。另外由于记录是跳跃式的移动，希尔排序并不是稳定的排序算法。