插入排序

直接插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
时间复杂度：
最好：正序 比较次数n 移动次数0
最坏：反序 比较次数n² 移动次数n²
平均：O(n²)
空间复杂度：O(1)
稳定性：稳定

利用二分查找实现插入排序
最好：正序 比较次数n * log n 移动次数0
最坏：反序 比较次数n * log n 移动次数n²
平均：O(n²)

数据越少、越接近有序排序性能越好

void InsertSort(int array[], int size) {
    for (int i = 1; i < size; i++) {
        int key = array[i];
        int j;
        for (j = i - 1; j >= 0 && array[j] > key; j--) {
            array[j + 1] = array[j];
        }
        array[j + 1] = key;
    }
}

// 利用二分查找实现插入排序
void InsertSortBS(int array[], int size) {
    for (int i = 1; i < size; i++) {
        // 有序 [0, i - 1]
        // 无序 [i, size - 1]
        int left = 0;
        int right = i - 1;
        // [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] == array[i]) {
                left = mid + 1;
            } else if (array[mid] < array[i]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // left 是要插入的位置的下标
        int key = array[i];
        for (int k = i; k > left; k--) {
            array[k] = array[k - 1];
        }
        array[left] = key;
    }
}

希尔排序

由于插入排序数据越少、越接近有序排序性能越好，希尔排序就是利用插入排序的这两个特点实现的，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
时间复杂度：
最好：O(n)
最坏：O(n²)
平均：O(1.3)
希尔排序的时间复杂度与增量的选取有关，Hibbard增量序列O(n^5/4)，Sedgewick增量序列O(n^7/6)
空间复杂度：O(1)
稳定性：不稳定

void InsertSortWithGap(int array[], int size, int gap) {
    for (int i = gap; i < size; i++) {
        int key = array[i];
        int j;
        for (j = i - gap; j >= 0 && array[j] > key; j -= gap) {
            array[j + gap] = array[j];
        }
        array[j + gap] = key;
    }
}

void ShellSort(int array[], int size) {
    int gap = size;
    while (1) {
        // 原始增量序列
        gap /= 2;
        // gap = gap / 3 + 1;
        InsertSortWithGap(array, size, gap);
        if (gap == 1) {
            break;
        }
    }
}