插入排序

直接插入排序

插入排序的基本操作就是将一个数据插入到已经排好的序列的有序数据中，从而得到一个新的、个数加1的有序数据，算法适用于少量数据的排序。 ** 时间复杂度为O(n^2),是稳定的排序方法。插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素排除(让数组多一个空间才有插入的位置)，而第二部分就只包含一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

void insert_sort(int* a, int len) {
    for (int i = 1; i < len; ++i) {
        int j = i - 1;
        int temp = a[i];
        while (temp < a[j] && j >= 0) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}

希尔排序

也称缩小增量排序，是直接插入排序算法一种更高效的改进版本。 ** 希尔排序是非稳定排序算法。 **

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

void shell_sort(int* a, int len) {
    int step = len / 2;
    int temp;

    while (step > 0) {
        for (int i = step; i < len; ++i) {
            temp = a[i];
            int j = i - step;
            while (j >= 0 && temp < a[j]) {
                a[j + step] = a[j];
                j -= step;
            }
            a[j + step] = temp;
        }
        step /= 2;
    }
}